树状数组与区间问题
树状数组与区间问题
0x00 引入树状数组
树状数组的作用
在做区间相关问题时，一般的线性表的效率太低，比如区间修改和查询一般是O(n), 而数组数组是O(logN)，在做大数据的区间更新和求和时，可以使用树状数组。
什么是树状数组
用数组来模拟树结构，只不过不是一般的树
树状数组的优缺点
修改和查询的复杂度都是O(logN)，而且相比线段树系数要少很多，比传统数组要快，而且容易写。缺点是遇到复杂的区间问题还是不能解决，功能还是有限。
0x01 普通树状数组
可以做到单点更新，区间查询
定义
以前学过二叉树，是这样的
当二叉树的每个结点保存的都是左右孩子的值，那么就变成了线段树
而树状数组是这样的
它的定义公式是
生成树
单点更新
根据定义可知，当实际数组A中的一个数据发生改变，则树状数组C会有多个位置发生改变，所以单点更新指的是原数组的单点更新，而在树状数组里其实是多个点更新了
而创建树的时候，直接把获得的数据拿去更新，就是建立树状数组了
代码实现
// i 为坐标 v 为要更新的值大小void update(int i, int v){for (; i<=MAX; i+=(i & -i)) BIT[i]+=v;}
区间查询
直接上代码，因为我们每次查询都是从 i 查询到开头，所以获取区间的实际操作是 query(y) - query(x - 1)
int query(int i){int ans=0;for (; i>0; i-=(i & -i)) ans+=BIT[i];return ans;}
0x02 变式
变式1 区更单查
如果想要区间更新，我们需要换一种方法建树—差分建树。
因为你如果使用普通的树状数组，区间更新需要对（x，y）每个值都进行update，一个update就是O(n)，一套下来就是（x，y）* O(n)，时间复杂度不允许，所以在这里引入差分建树，不过不是直接保存差值，而是区间差值之和。
规范A[0] = 0，不去使用第0项，直接从1开始，则树状数组每个点的值为
使用差分建树，是因为原数组区间更新，而区间差值不变，利用这个性质来建树。
//建树Loop() {cin >> a[i];update(i, a[i] - a[i - 1]);}//区间更新 (x, y)update(x, k), update(y - 1, -k); //第一次是 x ~ n加上 k ，第二次是 y ~ n 减掉 k，这样就能做到 x ~ y更新
可以区间更新的变式树状数组，其实和普通数组数组的差别就是，建树的时候采用了差分建树，其他没什么区别
变式2 区更区查
我们在变式1的基础上，稍作修改。
由上面的公式可知
此时我们只需要维护D[i] 和 D[i] * (i - 1) 这两部分就能做到区间查询了
int sum1[N], sum2[N];//更新void update(int i, int v) {int pos = i;for (; i<=MAX; i+=(i & -i)){sum1[i] += v;sum2[i] += v * (pos - 1)}}//查询int query(int i){int ans=0， pos = i;for (; i>0; i-=(i & -i)) {ans += pos * sum1[i] - sum2[i];}return ans;}
//建树Loop() {cin >> a[i];update(i, a[i] - a[i - 1]);}//区间更新 (x, y)update(x, k), update(y - 1, -k); //第一次是 x ~ n加上 k ，第二次是 y ~ n 减掉 k，这样就能做到 x ~ y更新//区间查询int sum = query(y) - query(x - 1);
若有收获，就点个赞吧
0 人点赞
