구간 합 구하기

Tree, RMQ(rmq)

출처: BOJ 구간 합 구하기

SOL)
 rmq를 이용하여 구간별 부분합을 빠르게 구한다.
업데이트는 자신과 조상들만 변경해주면 된다.



[-] Collapse

#include<stdio.h>
typedef long long ll;
ll rmq[4 * 1000000];

int main(){
    //freopen("input.txt", "r", stdin);
    int n, m, k, h = 1;
    scanf("%d%d%d", &n, &m, &k);
    while (h <= n) h <<= 1;
    for (int i = 0; i < n; i++)
        scanf("%lld", &rmq[i + h]);
    for (int i = h - 1; i >= 1; i--)
        rmq[i] = rmq[i * 2] + rmq[i * 2 + 1];

    for (int i = 0; i < m + k; i++){
        ll a, b, c; scanf("%lld %lld %lld", &a, &b, &c);
        if (a == 1){ //update
            b += h - 1;
            ll sub = c - rmq[b];
            while (b >= 1){
                rmq[b] += sub;
                b >>= 1;
            }
        }
        else{
            b += h - 1, c += h - 1;
            ll ans = 0;
            while (b <= c){ //segment sum
                if (b & 1) ans += rmq[b];
                if (!(c & 1)) ans += rmq[c];
                b = (b + 1) >> 1;
                c = (c - 1) >> 1;
            }
            printf("%lld\n", ans);
        }
    }
}