12/4

12/4

를 보고 update 기능이 있는 segment tree를 배웠다. 그래서

https://www.acmicpc.net/problem/2042

문제를 풀었고 다음과 같이 구현했다.

#include #include #define ll long long using namespace std; ll arr[1000000]; ll *sum; ll init(int node, int left, int right){ if (left == right) return sum[node] = arr[left]; int mid = (left + right)/2; return sum[node] = init(node*2, left, mid) + init(node*2+1, mid+1, right); } ll query(int left, int right, int node, int queryLeft, int queryRight){ if (left > queryRight || right < queryLeft) return 0; if (queryLeft <= left && right <= queryRight) return sum[node]; int mid = (left + right)/2; ll Lvalue = query(left, mid, node*2, queryLeft, queryRight); ll Rvalue = query(mid+1, right, node*2+1, queryLeft, queryRight); return Lvalue + Rvalue; } void update(int node, int left, int right, int idx, ll diff){ if (idx < left || idx > right) return; sum[node] += diff; if (left != right){ int mid = (left + right)/2; if (idx <= mid) return update(node*2, left, mid, idx, diff); update(node*2+1, mid+1, right, idx, diff); } } int main(){ ios::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; for (int i = 0; i < n; i++){ cin >> arr[i]; } int h = ceil(log2(n))+1; sum = new ll[1 << h]; for (int i = 1; i < (1 << h); i++){ sum[i] = 0; } init(1, 0, n-1); for (int i = 0; i < m+k; i++){ int a, b; ll c; cin >> a >> b >> c; if (a == 1){ update(1, 0, n-1, b-1, c-arr[b-1]); arr[b-1] = c; } else cout << query(0, n-1, 1, b-1, c-1) << '

'; } }

근데 n번째 줄에서 arr 값 또한 바꾸어야 diff가 올바르게 계산된다.

update()를 짜는 다른 방법으로는 djm03178님이 남긴 댓글을 참조해서 구현해볼 수 있다.

이 글을 보고 세그먼트 트리를 처음 접하는 분이 많을 것 같아서 팁을 하나 써봅니다.

개인적으로는 구간 합 구하기 문제에서 diff를 구해 그 변화를 반영하는 것보다는 원소의 값을 바꾸는 업데이트 자체를 세그먼트 트리가 수행하도록 하는 편이 더 간단하고 이해가 쉽다고 생각합니다.

예를 들어 본문의 그림에서 5번 원소를 업데이트 하는 경우 update 함수의 인자로 diff 대신 어떤 값으로 업데이트 하려는지 (k)를 전달해 주면, 리프 노드에서는 tree[node] = k; 를 수행해주면 되며, 그 부모 / 조상 노드들에서는 tree[node] = tree[node * 2] + tree[node * 2 + 1];을 수행하여 업데이트 해주면 됩니다. 이렇게 하면 매번 a 배열을 업데이트 해줘야 하는 번거로움도 없어지며, 이전 값을 기억하고 있어야 한다는 부담도 덜게 됩니다. 또한 세그먼트 트리의 각 노드가 항상 두 자식의 합을 가지고 있다는 의미 또한 더 명확해집니다.

물론 이 문제와는 관계 없이 변화량을 세그먼트 트리에 적용하는 테크닉 자체는 유용하게 사용될 수 있는 곳은 많이 있으니 알아두어도 나쁠 건 없습니다.

* 구현 추가

diff를 통해 구하는 위와 같은 방법은 사실 추후에 lazy propagation를 배울때 도움이 되는 아이디어라고 한다.

* segment tree 글 작성

from http://algops.tistory.com/18 by ccl(A) rewrite - 2021-12-04 12:01:15