之前找到一个数据结构与算法的课程，虽然是培训机构出的，不过听了下感觉还是不错的，主要详细介绍了一些高级数据结构与算法，视频还包含习题解析，后续会利用业余时间完成相应的内容，整理一些笔记。

本次回顾树状数组。

学习资料：

https://ke.qq.com/course/480225

https://www.bilibili.com/video/BV1rJ411Q7K8?from=search&seid=380339915135149037

参考资料：

《算法笔记》——胡凡

知识回顾

lowbit函数

假设

那么lowBit函数返回

实现如下：

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

备注：将$x$表示为二进制，那么$\mathrm{lowBit}(x)$返回$x$二进制最靠右边的$1$，以及其右边的$0$，所以

消去了$x$最靠右侧的$1$。

基本介绍

假设原数组为$A[1],\ldots, A[n]$，定义树状数组$C[1],\ldots,C[n]$（下标从$1$开始），其中

即$C[x]$管理位置$x$之前（包括$x$）$\text {lowbit}({x})$个元素。

树状数组结构：

适用场景：单点更新，区间查询。

前缀和

树状数组的主要应用场景是计算前缀和：

定义前缀和

那么

所以可以利用$C[n]$计算前缀和，代码如下：

int sum(int i){
    //计算a[1] + ... + a[i]
    int s = 0;
    while (i > 0){
        s += c[i];
        i -= lowBit(i);
    }

    return s;
}

时间复杂度：

每次消除最靠右侧的$1$，利用二进制表示可得时间复杂度为$O(\log n)$。

区间和

利用前缀和不难得到区间和的计算方式：

int sumRange(int i, int j) {
    //计算a[i] + ... + a[j] = sum(j) - sum(i - 1)
    return sum(j) - sum(i - 1);
}

单点更新

假设现在要对数组$A$进行更新， 特别的，我们要给$A[i]$增加$d$，那么所有包含$A[i]$的$C[j]$都要增加$d$，如果图中表示如下（虚线方向）：

显然$C[i]$要增加$d$，考虑下一个包含$A[i]$的$C[i+d]$，由树状数组的定义可得$C[i+d]$管理的元素数量必然要大于$C[i]$管理的元素数量，即

如果

那么由lowbit的定义可得

如果

那么

所以最小的

因此可得更新规则：

void add(int i, int x) {
    //nums[i] += x
    while (i <= n){
        c[i] += x;
        i += lowBit(i);
    }
}

二维情形

增加一重循环即可：

int c[maxn][maxn]; //二维树状数组
//二维add函数位置为(x,y)的整数加上v
void add(int x, int y, int v){
	for(int i = x; i < maxn; i += lowbit(i)){
		for(int j = y; j < maxn; j+= lowbit(j)){
			c[i][j] += v;
         }
     }
}

//二维getSum函数返回(1, 1)到(x, y)的子矩阵中元素之和
int getSum(int x, int y){
	int sum = 0;
	for(int i = x; i > 0; i -= lowbit(i)){
		for(int j = y; j > 0; j -= lowbit(j)){
         	sum += c[i][j];
         }
    }
	return sum;
}

例题

307. 区域和检索 - 数组可修改

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cstring>
#include <cstdlib>
#include <utility>
#include <climits>
using namespace std;

class NumArray {
public:
    int n;
    int* c;
    vector<int> nums;
    NumArray(vector<int>& nums) {
        this->nums = nums;
        n = nums.size();
        c = new int[n + 1];
        fill(c, c + n + 1, 0);
        //建bit
        for (int i = 1; i <= n; i++){
            c[i] += nums[i - 1];
            int j = i + lowBit(i);
            //后继节点在，则更新
            if (j <= n){
                c[j] += c[i];
            }
        }
    }

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

    void add(int i, int x) {
        //nums[i] += x
        i++;
        while (i <= n){
            c[i] += x;
            i += lowBit(i);
        }
    }

    void update(int i, int val) {
        //nums[i] = val
        add(i, val - nums[i]);
        //注意要更新nums, 否则后续更新有误
        nums[i] = val;
    }

    int sum(int i){
        //计算a[0] + ... + a[i]
        //增加索引
        i++;
        int s = 0;
        while (i > 0){
            s += c[i];
            i -= lowBit(i);
        }

        return s;
    }

    int sumRange(int i, int j) {
        //计算a[i] + ... + a[j] = sum(j) - sum(i - 1)
        return sum(j) - sum(i - 1);
    }
};

int main(){
    return 0;
}

304. 二维区域和检索 - 矩阵不可变

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <cstring>
#include <cstdlib>
using namespace std;

class NumMatrix {
public:
    int** cursum;
    NumMatrix(vector<vector<int>>& matrix) {
        int n = matrix.size();
        if (n == 0){
            return;
        }
        int m = matrix[0].size();
        int** c;
        c = new int*[n + 1];
        cursum = new int*[n + 1];
        for (int i = 0; i <= n; i++){
            c[i] = new int[m + 1];
            cursum[i] = new int[m + 1];
        }
        for (int i = 0; i <= n; i++){
            for (int j = 0; j <= m; j++){
                c[i][j] = 0;
                cursum[i][j] = 0;
            }
        }
        //建立二维树状数组
        //第一轮按行求每一维的树状数组
        for (int i = 1; i <= n; i++){
            for (int j = 1; j <= m; j++){
                c[i][j] += matrix[i - 1][j - 1];
                int k = j + lowBit(j);
                //后继点存在
                if (k <= m){
                    c[i][k] += c[i][j];
                }
            }
        }
        //第二轮按列求
        for (int j = 1; j <= m; j++){
            for (int i = 1; i <= n; i++){
                cursum[i][j] += c[i][j];
                int k = i + lowBit(i);
                //后继点存在
                if (k <= n){
                    cursum[k][j] += cursum[i][j];
                }
            }
        }
    }

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

    int sumCorner(int i, int j){
        int res = 0;
        for (int x = i; x > 0; x -= lowBit(x)){
            for (int y = j; y > 0; y -= lowBit(y)){
                res += cursum[x][y];
            }
        }

        return res;
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return sumCorner(row2 + 1, col2 + 1) + sumCorner(row1, col1) - sumCorner(row1, col2 + 1) - sumCorner(row2 + 1, col1);
    }
};

int main(){
    return 0;
}