2042번: 구간 합 구하기

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


$O(n+(m+k)\lg n)$

bit를 사용해서 해결하자.
참고로 채점 데이터에 b,c 값이 long long 범위인 경우가 있는 것 같으니 유의하자.

#include<stdio.h>
const int MAX_N = 1e6;
typedef long long ll;
ll bit[MAX_N + 1], a[MAX_N + 1];
int n, m, k;
void update(int h, ll x) {
    for (int i = h; i <= n; i += i&-i) bit[i] += x;
}
ll query(int h) {
    ll r = 0;
    for (int i = h; i; i -= i&-i) r += bit[i];
    return r;
}
int main() {
    scanf("%d %d %d", &n, &m, &k);
    for (int i = 1; i <= n; i++) scanf("%d", a + i), update(i, a[i]);
    ll x, y, z;
    for (int i = 0; i < m + k; i++) {
        scanf("%lld %lld %lld", &x, &y, &z);
        if (x == 1) update(y, z - a[y]), a[y] = z;
        else printf("%lld\n", query(z) - query(y - 1));
    }
    return 0;
}