====== 수열과 쿼리 17 ====== ===== 풀이 ===== * [[ps:구간 쿼리#구간 최솟값|업데이트 쿼리와 구간 최솟값 쿼리]]가 주어지는 문제이다. * 세그먼트 트리를 이용해서 업데이트와 구간최솟값 쿼리를 모두 O(logn)에 처리 가능하다. * [[ps:구간 쿼리#구간 합]]과는 달리, 펜윅트리는 일반적인 방법으로는 적용이 불가능하다. * 펜윅트리 2개를 조합해서 처리하는 방법이 존재하긴 하고, 그 방법이 더 빠르다고는 하다. [[ps:펜윅 트리]] 참고. 하지만 구현해보지는 않았다 * 세그먼트 트리를 구축하는 데에 O(n)이 걸리고 m개의 쿼리를 각각 O(logn)에 처리하므로, 총 시간 복잡도는 O(n+mlogn) ===== 코드 ===== """Solution code for "BOJ 14438. 수열과 쿼리 17". - Problem link: https://www.acmicpc.net/problem/14438 - Solution link: http://www.teferi.net/ps/problems/boj/14438 """ import sys from teflib import segmenttree def main(): N = int(sys.stdin.readline()) # pylint: disable=unused-variable A = [int(x) for x in sys.stdin.readline().split()] segtree = segmenttree.SegmentTree(A) M = int(sys.stdin.readline()) for i in range(M): query = [int(x) for x in sys.stdin.readline().split()] if query[0] == 1: _, i, v = query segtree.set(i - 1, v) else: _, i, j = query print(segtree.query(i - 1, j)) if __name__ == '__main__': main() * Dependency: [[:ps:teflib:segmenttree#SegmentTree|teflib.segmenttree.SegmentTree]] {{tag>BOJ ps:problems:boj:골드_1}}