[BOJ] 백준 2268 수들의 합

출처: https://www.acmicpc.net/problem/2268

#세그먼트 트리 #구간 합

 Input 

3 5

0 1 3

1 1 2

1 2 3

0 2 3

0 1 3

　 

 Output 

0

3

5　

세그먼트 트리 구조를 구현하는 문제입니다.

* 자료 범위가 long long 타입이 요구됩니다.

* 주어지는 query 하는 구간이 i > j 일 수 있으므로 swap 처리가 필요합니다.

- 특정 위치의 값을 수정하는 update()

void update(LL tree[], int now, int s, int e, int pos, int val) {
       if (s == e) {
              tree[now] = val;
              return;
       }
       int L = now * 2, R = L + 1, mid = (s + e) / 2;
       if(pos <= mid) update(tree, L, s, mid, pos, val);
       else update(tree, R, mid + 1, e, pos, val);
       tree[now] = tree[L] + tree[R];
}

- 특정 구간의 합을 구하는 query()

LL query(LL tree[], int now, int s, int e, int qs, int qe) {
       if (e < qs || qe < s) return 0;
       if (qs <= s && e <= qe) return tree[now];
       int L = now * 2, R = L + 1, mid = (s + e) / 2;
       return query(tree, L, s, mid, qs, qe) + query(tree, R, mid + 1, e, qs, qe);
}

- 단말 노드 크기는 1 ≤ N ≤ 1,000,000 이므로 Tree Size는 {단말노드 개수 × 4} 정도로 잡습니다.

  (update, query 호출횟수는 최대 1,000,000 (=M) 입니다.)

- query() 결과만 출력합니다.

  (문제 조건 "1" update, "0" query)

---

#include <stdio.h>
 
typedef long long LL;
const int MAX_N = 1e6 + 5;
int N, M, cmd;
int pos, val, qs, qe;
LL tree[4 * MAX_N];
inline void swap(int& A, int& B) { int temp = A; A = B; B = temp; }
void update(LL tree[], int now, int s, int e, int pos, int val) {
    if (s == e) {
        tree[now] = val;
        return;
    }
    int L = now * 2, R = L + 1, mid = (s + e) / 2;
    if (pos <= mid) update(tree, L, s, mid, pos, val);
    else update(tree, R, mid + 1, e, pos, val);
    tree[now] = tree[L] + tree[R];
}
 
LL query(LL tree[], int now, int s, int e, int qs, int qe) {
    if (e < qs || qe < s) return 0;
    if (qs <= s && e <= qe) return tree[now];
    int L = now * 2, R = L + 1, mid = (s + e) / 2;
    return query(tree, L, s, mid, qs, qe) + query(tree, R, mid + 1, e, qs, qe);
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &M);
 
    while (M--) {
        scanf("%d", &cmd);
        if (cmd) {
            scanf("%d %d", &pos, &val);
            update(tree, 1, 1, N, pos, val);
        }
        else {
            scanf("%d %d", &qs, &qe);
            if (qs > qe) swap(qs, qe);
            printf("%lld\n", query(tree, 1, 1, N, qs, qe));
        }
    }
}