Segment Tree -구간 합

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 61 62 63 64 65 66 67 68

#include <stdio.h> #define SUM(x,y) ((x)+(y))   int N, Q; int tree[1 << 17]; int maps[200000];   void update(int node, int s, int e, int idx, int add_data) {     int m;     if (s == e) {         tree[node] += add_data;         return;     }     m = (s + e) / 2;     if (idx <= m) update(node * 2, s, m, idx, add_data);     else update(node * 2 + 1, m+1, e, idx, add_data);     tree[node] = SUM(tree[node * 2], tree[node * 2 + 1]); }   void add(int node, int s, int e, int idx, int data) {     int m;     if (s == e) {         tree[node] = data;         return;     }     m = (s + e) / 2;     // 왼쪽 구간     if (idx <= m) add(node * 2, s, m, idx, data);     // 오른쪽 구간     else add(node * 2 + 1, m + 1, e, idx, data);     tree[node] = SUM(tree[node * 2], tree[node * 2 + 1]); }   int query(int node, int rs, int re, int qs, int qe) {     int m, l, r;     if (qs <= rs && re <= qe) return tree[node];     if (qs > re || rs > qe) return 0;     m = (rs + re) / 2;     l = query(node * 2, rs, m, qs, qe);     r = query(node * 2 + 1, m + 1, re, qs, qe);     return SUM(l, r); }     int main() {     //freopen("input.txt", "r", stdin);     int i, num, qs, qe, idx, add_data;     scanf("%d %d", &N, &Q);     for (i = 1; i <= N; i++) {         scanf("%d", &num);         add(1, 1, N, i, num);     }     for (i = 1; i <= Q; i++) {         scanf("%d %d %d %d", &qs, &qe, &idx, &add_data);         printf("%d\n",query(1, 1, N, qs, qe));         update(1, 1, N, idx, add_data);     }     return 0; }   /**************************************************************     Problem: 2861     User: AXQ6548     Language: C     Result: Accepted     Time:259 ms     Memory:2376 kb ****************************************************************/