ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study（树状数组）

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define INF 0x3f3f3f3f
const int N = 1e5 + 10;
const int M = 1e2 + 5;

int n, q;
ll c1[N], c2[N], a[N];

void upd(int x, ll val){
    ll t = val * (n-x+1);
    while(x <= n){
        c1[x] += val;           // 普通前缀和
        c2[x] += t;             // 题目前缀和
        x += (x&-x);
    }
}   
ll sum1(int x){
    ll res = 0;
    while(x > 0){
        res += c1[x];
        x -= (x&-x);
    }
    return res;
}
ll sum2(int x){
    ll res = 0;
    while(x > 0){
        res += c2[x];
        x -= (x&-x);
    }
    return res;
}

int main(){
    scanf("%d%d", &n, &q);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &a[i]);
        upd(i, a[i]);
    }
    while(q--){
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        if(x == 1){
            ll ans1 = sum1(z) - sum1(y-1);
            ll ans2 = sum2(z) - sum2(y-1);
            printf("%lld\n", ans2 - ans1 * (n - z));
        }else{
            ll t = z - a[y];  // 增量
            a[y] = z;     
            upd(y, t);
        }
    }
    return  0;
}
/*
 */