세그먼트 트리

#include <cstdio>

#define max 2097152 // 2^21

long long sum(int l, int r, int nl, int nr, int nodeNum);

void update(int i, int v);

long long num[max];

int main() 

{

int a, b, c, n, m, k, rn;

scanf("%d %d %d", &n, &m, &k);

for (rn = 1; rn < n; rn *= 2);

for (int i = rn - 1; i < rn - 1 + n; scanf("%lld", &num[i++]));

for (int i = rn - 2; i > -1; --i)

num[i] = num[i * 2 + 1] + num[i * 2 + 2];

for (int i = 0; i < m + k; ++i)

{

scanf("%d %d %d", &a, &b, &c);

if (a == 2)

printf("%lld\n", sum(b - 1, c - 1, 0, rn - 1, 0));

else

update(b + rn - 1, c);

}

}

long long sum(int l, int r, int nl, int nr, int nodeNum)

{

if (r < nl || nr < l)

return 0;

if (l <= nl && nr <= r)

return num[nodeNum];

return sum(l, r, nl, (nl + nr) / 2, nodeNum * 2 + 1) + sum(l, r, ((nl + nr) / 2) + 1, nr, nodeNum * 2 + 2);

}//l,r은 내가 구하려는 값, nl, nr은 노드의 좌우값, nodeNum은 현재 노드 번호.

void update(int i, int v)

{

num[i - 1] = v;

for (i /= 2; i > 0; i /= 2)

num[i - 1] = num[2 * i - 1] + num[2 * i];

}//구한거를 차례대로 갱신.