树状数组两种修改+求和 | 模板

\(O(mlogn)\)，单次查询为\(O(logn)\)

实际最坏情况下优于线段树，因为跑不满...

1.单点修改+区间求和

区间求和变为前缀和相减。

#include<iostream>
#include<cstdio>

const int maxn = 5e5 + 7;
int n, m;
int num;
int c[maxn];

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

int sum(int x) {
    int ans = 0;
    while (x) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

void add(int x, int k) {
    while (x <= n) {
        c[x] += k;
        x += lowbit(x);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &num);
        add(i, num);
    }
    while (m--) {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 1) add(x, y);
        if (opt == 2) printf("%d\n", sum(y) - sum(x - 1));
    }
    return 0;
}

2.区间修改+单点查询

区间修改\([x,y]\)：做差分，令\(C[x]+=k,C[y+1]-=k\)

单点查询：即差分数列的前k项和

\(O()\)

#include<iostream>
#include<cstdio>

const int maxn = 5e5 + 7;
int n, m;
int num;
int c[maxn], input[maxn];

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

int query(int x) {
    int ans = 0;
    while (x != 0) {
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}

void add(int x, int k) {
    while (x <= n) {
        c[x] += k;
        x += lowbit(x);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &input[i]);
    }
    while (m--) {
        int opt, x, y, k;
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d%d%d", &x, &y, &k);
            add(x, k);
            add(y + 1, -k);
        }
        if (opt == 2) {
            scanf("%d", &x);
            printf("%d\n", input[x] + query(x));
        }
    }
    return 0;
}