백준[19951] 태상이의 훈련소 생활

문제 설명

문제 링크

http://icpc.me/19951

19951번: 태상이의 훈련소 생활

풀이

세그먼트 트리를 이용하여 풀이하였다.

하지만 누적합을 이용하여 더 쉽게 풀이할 수 있는 것 같다.

수열과 쿼리21과 문제가 비슷하여 똑같이 풀이하였다. 자세한 풀이는 저 링크를 참고하자.

코드

#include <cstdio>

int seg[400005], arr[100005];

void init(int node, int s, int e) {
    if (s == e) {
        seg[node] = arr[s];
        return;
    }
    int mid = (s + e) >> 1;
    init(2 * node, s, mid);
    init(2 * node + 1, mid + 1, e);
}

void update(int node, int s, int e, int qs, int qe, int num) {
    if (e < qs || qe < s) return;
    if (qs <= s && e <= qe) {
        seg[node] += num;
        return;
    }
    int mid = (s + e) >> 1;
    update(2 * node, s, mid, qs, qe, num);
    update(2 * node + 1, mid + 1, e, qs, qe, num);
}

int query(int node, int s, int e, int idx, int ans) {
    if (e < idx || idx < s) return 0;
    ans += seg[node];
    if (s == e) return ans;
    int mid = (s + e) >> 1; 
    return query(2 * node, s, mid, idx, ans) + query(2 * node + 1, mid + 1, e, idx, ans);
}

int main() {
    int n, m; scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", arr + i);
    }
    init(1, 0, 1e5);
    while (m--) {
        int s, e, num; scanf("%d %d %d", &s, &e, &num);
        update(1, 0, 1e5, s, e, num);
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", query(1, 0, 1e5, i, 0));
    }
}