前置知识

lowbit

求出最后一个二进制中最后一个1在什么位置

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

原理:原码 & 补码

例如：11 & (-11)

11原码: 0000 1011

-11原码: 1000 1011

-11反码: 1111 0100

-11补码: 1111 0101

  0000 1011 
& 1111 0101
 -----------
  0000 0001

简介

用于快速处理单点修改和求前缀和问题的数据结构，时间复杂度为\(log(n)\)。

功能模块

查询前缀和

int c[N]
inline int query(int x) {
    int sum = 0;
    for (; x; x -= x & (-x)) {
        s += c[x];
    }
}

单点修改

int c[N];
inline void modify(int x, int val) {
    for (; x <= n; x += x & (-x)) {
        c[x] += val;
    }
}

树状数组二分

从高到低，每位二进制看看是否能取1

inline long long query(long long s) {
    long long t = 0;
    int pos = 0;
    for (int j = 18; j >= 0; j--) {
        if (pos + (1 << j) <= n && t + c[pos + (1 << j)] <= s) {
            pos = pos + (1 << j);
            t += c[pos];
        }
    }
    return pos;
}

单点查询

运用差分思想，把维护一个差分的树状数组

#include <bits/stdc++.h>

using namespace std;

/* 
    树状数组 + 差分应用
    实现区间加 + 求前缀和
    a[1] = d1
    a[2] = d1 + d2
    a[3] = d1 + d2 + d3
    ...
    S[1 - 3] = a[1] + a[2] + a[3]
             = d1 + d1 + d2 + d1 + d2 + d3
             = 3d1 + 2d2 + d3
             = (x + 1 - i) * di
             = (x + 1) * Sdi - S*i*di
    维护d 和 i*d 两个数组
 */

typedef long long ll;
typedef unsigned long long u64;
const int N = 2010000;

int n, q;
int a[N];

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

template<class T>
struct BIT {
    T c[N];
    int size = 0;
    void resize(int s) {
        size = s;
    }
    void modify(int x, T val) {
        for (; x <= size; x += lowbit(x)) {
            c[x] += val;
        }
    }
    T query(int x) {
        T s = 0;
        for (; x; x -= lowbit(x)) {
            s += c[x];
        }
        return s;
    }
};

BIT<u64> c1, c2;

 int main() {
    scanf("%d%d", &n, &q);
    c1.resize(n), c2.resize(n);
    for (int i = 0; i < q; i++) {
        int ty;
        scanf("%d",&ty);
        if (ty == 1) {
            int l, r;
            u64 d;
            scanf("%d%d%llu",&l,&r,&d);
            c1.modify(l, d);
            c1.modify(r + 1, -d);
            c2.modify(l, l * d);
            c2.modify(r + 1, (r + 1) * (-d));
        } else {
            int x;
            scanf("%d",&x);
            u64 ans = (x + 1) * c1.query(x) - c2.query(x);
            printf("%llu\n",ans);
        }
    }
 }

高维树状数组

和一维一样进行处理

#include <bits/stdc++.h>

using namespace std;   

const int N = 503;

/* 
    高维树状数组
    和一维没什么区别
 */

long long c[N][N];
int a[N][N];
int n, m, q;

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

inline void modify(int x, int y, long long v) {
    for (int p = x; p <= n; p += lowbit(p)) {
        for (int q = y; q <= m; q += lowbit(q)) {
            c[p][q] += v;
        }
    }
}

inline long long query(int x, int y) {
    long long s = 0;
    for (int p = x; p; p -= lowbit(p)) {
        for (int q = y; q; q -= lowbit(q)) {
            s += c[p][q];
        }
    }
    return s;
}


int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d",&a[i][j]);
            modify(i, j, a[i][j]);
        }
    }
    for (int i = 1; i <= q; i++) {
        int ty;
        scanf("%d",&ty);
        if (ty == 1) {
            int x, y, d;
            scanf("%d%d%d",&x,&y,&d);
            modify(x, y, d - a[x][y]);
            a[x][y] = d;
        } else {
            int x, y;
            scanf("%d%d",&x,&y);
            printf("%lld\n",query(x, y));
        }
    }
}

树状数组模板

template<class T>
struct BIT {
    T c[N];
    int size;
    void resize(int s) { size = s; }
    void modif(int x, T d) {
        assert(x != 0);
        for (; x <= size; x += x & (-x)) {
            c[x] += d;
        }
    }
    T query(int x) {
        assert(x<=size);
        T s = 0;
        for (; x; x -= x & (-x)) {
            s += c[x];
        }
        return s;
    }
};