구간 합1 펜윅 트리 쉽게 이해하기. 알고리즘에 입문을 해서 문제를 풀다 보면 구간 합과 관련된 문제를 접하게 된다. 우리는 구간 합 문제를 O(N) 복잡도의 누적 합을 구하고 특정 구간의 원소들의 합을 O(1) 만에 구할 수 있는 방법을 습득하게 된다. 누적 합이 몇인지 묻는 질의(또는 쿼리)가 M개가 주어진다면, 우리는 O(M)의 복잡도로 문제를 빠르게 해결할 수 있다. 만약, 위와 같은 질의 중간중간에 원소의 값이 바뀌는 새로운 질의가 주어진다면 어떻게 해결해야 할까? 매번 O(N)을 수행해서 누적 합을 저장하는 배열의 값을 업데이트해주어야 할까? 그럼 O(NM)의 복잡도로 시간 초과를 받게 될 것이다. 구간 트리 또는 세그먼트 트리(segment tree)라는 것이 있지만 누적 합과 관련된 문제에서 좀 더 간단하게 구현할 수 있는 펜.. 2023. 7. 21. 이전 1 다음
