树状数组

动态区间和询问 + 点修改

int lowbit(int x){
    return x & -x;
}

void add(int x, int v){
    for(int i = x; i <= n; i += lowbit(i)) tree[i] += v;
}

int query(int x){
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tree[i];
    return res;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ){
        cin >> a[i];
        add(i, a[i]);
    }
    
    while(m--){
        int k, a, b; cin >> k >> a >> b;
        if(!k) cout << query(b) - query(a - 1) << endl; //区间和询问
        else add(a, b);    //点修改
    }
}

点询问 + 区间修改

int lowbit(int x){
    return x & (-x);
}

void add(int x, int c){
    for(int i = x; i < N; i += lowbit(i)) tree[i] += c;
}

int query(int x){
    int res = a[x];
    for(int i = x; i; i -= lowbit(i)) res += tree[i];
    return res;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];

    while(m -- ){
        char op; cin >> op;
        if(op == 'Q'){
            int x; cin >> x;
            cout << query(x) << endl;
        }else{
            int l, r, c; cin >> l >> r >> c;
            add(l, c), add(r + 1, -c);
        }
    }

    return 0;
}

动态区间和询问 + 区间修改

ll tree[2][N];  //tree[0][]维护bi, tree[1][]维护i*bi
ll pre[N];      //初始前缀和
ll a[N];
int n, m;

int lowbit(int x){
    return x & (-x);
}

void add(int flag, int x, int d){
    for(int i = x; i <= n; i += lowbit(i)) tree[flag][i] += (ll)d;
}

ll query(int flag, int x){
    ll res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tree[flag][i];
    return res;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++ )
        cin >> a[i], pre[i] = pre[i - 1] + a[i];

    while(m -- ){
        char op; cin >> op;
        if(op == 'Q'){
            int l, r; cin >> l >> r;
            ll res = 0;
            res += pre[r] + (r + 1) * query(0, r) - query(1, r);
            res -= pre[l - 1] + l * query(0, l - 1) - query(1, l - 1);
            cout << res << endl;
        }else{
            int l, r, d; cin >> l >> r >> d;
            add(0, l, d), add(0, r + 1, -d);
            add(1, l, l * d), add(1, r + 1, (r + 1) * (-d));
        }
    }

    return 0;
}

树状数组求逆序对

int lowbit(int x){
    return x & (-x);
}

void add(int x, int c){
    for(int i = x; i < N; i += lowbit(i)) tree[i] += c;
}

int query(int x){
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tree[i];
    return res;
}

int main(){
    cin >> n;
for(int i = 1; i <= n; i ++ ) cin >> h[i], h[i] ++ ; 
//有可能存在身高为0的人 (卧槽！？)  
    for(int i = 1; i <= n; i ++ ){  //正序遍历 统计前面比h[i]高的人
        cnt[i] += query(N - 1) - query(h[i]);  //区间和为大于身高h[i]的区间内人数之和
        add(h[i], 1);    //该身高人数 + 1
    }

    memset(tree, 0, sizeof(tree));   //树状数组重新初始化 
    for(int i = n; i; i -- ){  //倒序遍历 统计后面比h[i]严格小的人
        cnt[i] += query(h[i] - 1);    //区间和为严格小于h[i]的区间内人数之和
        add(h[i], 1);    //该身高人数 + 1
}

    ll res = 0;  //累加不高兴度
    for(int i = 1; i <= n; i ++ )
        res += (ll)(1 + cnt[i]) * cnt[i] / 2;   //等差数列求和
    cout << res;

    return 0;
}

线段树

区间最值询问 + 点修改

struct node{
    int l, r, maxv;
}tree[4 * N];
typedef long long ll;
int n = 0;

void build(int u, int l, int r){
    tree[u] = {l, r};
    if(l == r) return;
    int mid = (l + r) >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

//区间最值询问
int query(int u, int l, int r){
    if(tree[u].l >= l && tree[u].r <= r) return tree[u].maxv;
    int mid = (tree[u].l + tree[u].r) >> 1;
    int v = 0;
    if(l <= mid) v = query(u << 1, l, r);
    if(r > mid) v = max(v, query(u << 1 | 1, l, r));
    return v;
}

//点修改
void modify(int u, int x, int v){
    if(tree[u].l == tree[u].r) tree[u].maxv = v;
    else{
        int mid = (tree[u].l + tree[u].r) >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        tree[u].maxv = max(tree[u << 1].maxv, tree[u << 1 | 1].maxv);
    }
}