• API
• FAQ
• Tools
• Archive
A Pastebin account makes a great Christmas gift
SHARE
TWEET

# Untitled

a guest Mar 13th, 2018 52 Never
ENDING IN00days00hours00mins00secs

1. #include <cstdio>
2. #include <iostream>
3.
4. typedef long long int ll;
5. int n, m, k;
6. ll arr[1000001];
7. ll tree[3000100];
8.
9. ll makeTree(int left,int right,int node ) {
10.
11.     if (left == right) { //기저사례
12.         return tree[node] = arr[left];
13.     }
14.
15.     int mid = (left + right) / 2;
16.
17.     tree[node] += makeTree(left, mid, node * 2);//왼쪽 노드 합
18.     tree[node] += makeTree(mid + 1,right, node * 2 +1);//오른쪽 노드 합
19.
20.     return tree[node];
21. }
22.
23. void upDate(int left,int right,int node, int change_node ,ll diff) {
24.
25.     if (!(left <= change_node &&change_node <= right))return; //영향이 없으므로...
26.
27.     tree[node] += diff;
28.
29.     if (left != right) {
30.         int mid = (left + right) / 2;
31.         upDate(left, mid, node * 2, change_node, diff);
32.         upDate(mid +1,right, node * 2 +1, change_node, diff);
33.     }
34. }
35.
36. ll sum(int node, int left, int right, int start, int end) {
37.
38.     if (right < start || end < left)return 0; //구간밖
39.
40.     if (start <= left && right <= end)return tree[node];//포함관계라면
41.
42.     int mid = (left + right) / 2;
43.
44.     return sum(node * 2, left, mid, start, end)+sum(node*2+1,mid+1,right,start,end);
45. }
46. int main() {
47.
48.     scanf("%d %d %d", &n, &m, &k);
49.     for (int i = 1; i <= n; i++)scanf("%lld", &arr[i]);
50.
51.     //구간합 트리만들기
52.     makeTree(1, n, 1);
53.
54.     for (int i = 0; i < k + m; i++) {
55.         int cmd, b;ll c;
56.         scanf("%d %d %lld", &cmd, &b, &c);
57.
58.         if (cmd == 1) { //변경
59.             ll diff = c - arr[b];
60.             arr[b] = c;
61.             upDate(1, n, 1, b, diff);//1부터 n까지 1(루트)부터시작, b인덱스변경
62.         }
63.         else { //합 출력
64.             // 1(루트부터) 1부터n범위탐색해서 b부터 c구간합 찾기
65.             printf("%lld\n", sum(1, 1, n , b , c));
66.         }
67.     }
68. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.

Top