<링크>
https://www.acmicpc.net/problem/2042
<소스코드>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 | #include<stdio.h> typedef long long ll; ll tree[3000000]; ll num[1000001]; ll init(int, int, int); void update(int, int, int, int, int); ll sum(int, int, int, int, int); int main() { int N, M, K; scanf("%d%d%d", &N, &M, &K); for (int i = 1; i <= N; ++i) scanf("%lld", num + i); init(1, 1, N); for (int i = 0; i < M + K; ++i) { int a, b, c; scanf("%d%d%d", &a, &b, &c); if (a == 1) { int diff = c - num[b]; num[b] = c; update(1, 1, N, b, diff); } else printf("%lld\n", sum(b, c, 1, 1, N)); } } void update(int n, int s, int e, int t, int diff) { if (s <= t && t <= e) tree[n] += diff; else return; if (s == e) return; int m = (s + e) / 2; update(n * 2, s, m, t, diff); update(n * 2 + 1, m + 1, e, t, diff); } ll sum(int l, int r, int n, int s, int e) { if (l <= s && e <= r) //구하는구간이 노드의구간을 포함할때 return tree[n]; if (r < s || e < l) //아예 벗어나있을때 return 0; //어중간하게 겹칠때 int m = (s + e) / 2; return sum(l, r, n * 2, s, m) + sum(l, r, n * 2 + 1, m + 1, e); } ll init(int n, int s, int e)//n번노드는 s~e를 맡는다 { if (s == e) return tree[n] = num[s]; int m = (s + e) / 2; tree[n] = init(n * 2, s, m) + init(n * 2 + 1, m + 1, e); return tree[n]; } | cs |
<풀이>
세그먼트 트리 (Segment Tree)
https://www.acmicpc.net/blog/view/9
●init
n번노드는 s~e를 맡는다.
세그먼트트리를 만들때, 자식노드들은 n*2, n*2+1 로 퍼져나가고 각각이 맡는 범위는 s~절반, 절반+1~e까지이다.
노드 자체에 자신이 맡는 범위가 명시돼있지 않으므로 재귀 호출할 때 인자로 노드의 번호와 함께 맡는 범위를 같이 넘겨줘야한다. leaf노드까지 도달하면(s==e) 자기자신의 값을 저장하고 리턴한다.
●sum
합을 구할때는 해당노드가 맡는 범위(s~e)가 아예 구하고자하는 범위(l~r)에 속하지 않을때는 0을 리턴하고
완전 포함되어있을때는 그 노드의 값을 리턴한다.
위 둘중 하나가 아니라면
계속 반으로 쪼개서 재귀호출하여 리턴한다.
●update
해당노드가 포함되는 모든 노드들을 갱신시켜주면되는데 아예 포함되지 않을 경우는 그냥 리턴하고
leaf노드까지 도달하면(s==e) 리턴한다.
계속 반으로 쪼개서 재귀호출하고 수정한다.
여기서 깜빡하고 노드들의 합만 바꿔주고 배열 자체의 값은 바꾸지 않아서 많이 헤맸다.
