2268번: 수들의 합

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


$O(mlgn)$

bit를 구현한다.

#include<cstdio>
typedef long long lint;
const int MAX_N = 1e6;
int n, m, a[MAX_N + 1];
lint bit[MAX_N + 1];
void f(int x, int y) {
    for (int j = x; j <= n; j += j&-j) bit[j] += y;
}
lint g(int x) {
    lint r = 0;
    for (int j = x; j; j -= j&-j) r += bit[j];
    return r;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        if (x) f(y, z - a[y]), a[y] = z;
        else printf("%lld\n", z>y ? g(z) - g(y - 1) : g(y) - g(z - 1));
    }
    return 0;
}