树状数组

2021-01-02

树状数组

树状数组（Binary Indexed Tree/Fenwick Tree）。

视频：https://www.bilibili.com/video/BV1Hz411v7XC?p=2

1. 引入-前缀和

给定一个数组，有多个区间和查询，如何快速高效的给出区间 $[i:j]$ 的和呢？容易想到可以构造一个前缀和数组 prefix，prefix[i]表示了前i项数字的和（包含第i项），那么区间 $[i:j]$ 的和即：prefix[j] - prefix[i-1]。

例子，给定数组 $[1,2,3,4,5]$，可得到前缀和数组：$[1,3,6,10,15]$，求第2-4项之和，等于$10-1=9$。

可以看到，构造好前缀和数组之后，区间查询操作的时间复杂度为$O(1)$。

问题来了，当存在修改数组某个数的操作，然后再求区间和呢？当修改了某个数字之后，其后面的前缀和也都要修改，时间复杂度为$O(n)$。本文介绍的树状数组在区间查询、单点更新的时间复杂度都是$O(\log_2 n)$。

树状数组的基本思想就是将前缀和表示为多个子区间的和。那到底该如何表示，使得单点更新操作更加高效呢？

这就用到了二进制的思想。

2. lowbit操作

注意：计算机如何表示负数？对应的正数取反加一。
已知一个八位的计算机系统，问有符号二进制数”10000000”转换为十进制数是多少？A：-128 。最高位表示符号位。
C++中存在short和unsigned short数据类型，他们分别占多少字节，取值范围分别为多少？A：两者都占2个字节（16位bits）。unsigned short只能表示0-65535的正数，而short表示的是-32768~32767的数。两种数据类型的区别就是short的最高位是符号位（0表示正数，1表示负数）。

3. 题目测试

题目链接：https://www.luogu.com.cn/problem/P3374

#include <iostream>

using namespace std;
int n, m;
long long nums[500010], bit[500010];
int lowbit(int n){
    return n & (-n);
}
void build(long long nums[], long long bit[]){
    for(int i = 0; i < n; i++){
        bit[i + 1] = nums[i];
    }
    for(int i = 1; i < n; i++){
        int j = i + lowbit(i);
        if(j <= n){
            bit[j] += bit[i];
        }
    }
}
void update(int idx, int num){
    idx += 1;
    while(idx <= n){
        bit[idx] += num;
        idx += lowbit(idx);
    }
}
int prefixSum(int idx){
    idx += 1;
    int res = 0;
    while(idx > 0){
        res += bit[idx];
        idx -= lowbit(idx);
    }
    return res;
}
int rangeSum(int start, int ends){
    return prefixSum(ends) - prefixSum(start - 1);
}
int main()
{
    int types, a, b;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> nums[i];
    }
    build(nums, bit);
    for(int i = 0; i < m; i++){
        cin >> types >> a >> b;
        if(types == 1){
            update(a - 1, b);
        }else{
            cout << rangeSum(a - 1, b - 1) << endl;
        }
    }
    return 0;
}

未完待续…