VioletaBabel
세그먼트 트리 본문
#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];
}//구한거를 차례대로 갱신.
'알고리즘' 카테고리의 다른 글
원형 큐 (c/c++) (0) | 2018.12.06 |
---|---|
플로이드-와샬 알고리즘 (0) | 2017.06.23 |
최대공약수, 최소공배수 (0) | 2017.05.28 |
[C++/함수]에라토스테네스의 체 (0) | 2017.05.28 |
단순한 이진트리 코드 (0) | 2017.04.29 |