先来看几个问题吧.
1. 什么是树状数组?
顾名思义, 就是用数组来模拟树形结构呗. 那么衍生出一个问题, 为什么不直接建树? 答案是没必要, 因为树状数组能处理的问题就没必要建树. 和 Trie 树的构造方式有类似之处.
2. 树状数组可以解决什么问题
可以解决大部分基于区间上的更新以及求和问题.
3. 树状数组和线段树的区别在哪里
树状数组可以解决的问题都可以用线段树解决, 这两者的区别在哪里呢? 树状数组的系数要少很多, 就比如字符串模拟大数可以解决大数问题, 也可以解决 1+1 的问题, 但没人会在 1+1 的问题上用大数模拟.
4. 树状数组的优点和缺点
修改和查询的复杂度都是 O(logN), 而且相比线段树系数要少很多, 比传统数组要快, 而且容易写.
缺点是遇到复杂的区间问题还是不能解决, 功能还是有限.
一, 树状数组介绍
二叉树大家一定都知道, 如下图
如果每个父亲都存的是两个儿子的值, 是不是就可以解决这类区间问题了呢. 是的没错, 但是这样的树形结构, 叫做线段树.
那真的的树形结构是怎样的, 和上图类似, 但省去了一些节点, 以达到用数组建树.
黑色数组代表原来的数组 (下面用 A[i] 代替), 红色结构代表我们的树状数组 (下面用 C[i] 代替), 发现没有, 每个位置只有一个方框, 令每个位置存的就是子节点的值的和, 则有
- C[1] = A[1];
- C[2] = A[1] + A[2];
- C[3] = A[3];
- C[4] = A[1] + A[2] + A[3] + A[4];
- C[5] = A[5];
- C[6] = A[5] + A[6];
- C[7] = A[7];
- C[8] = A[1] + A[2] + A[3] + A[4] + A[5] + A[6] + A[7] + A[8];
可以发现, 这颗树是有规律的
C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i]; //k 为 i 的二进制中从最低位到高位连续零的长度
例如 i = 8(1000)时候, k = 3, 可自行验证.
这个怎么实现求和呢, 比如我们要找前 7 项和, 那么应该是 SUM = C[7] + C[6] + C[4];
而根据上面的式子, 容易的出 SUMi = C[i] + C[i-2k1] + C[(i - 2k1) - 2k2] + .....;
其实树状数组就是一个二进制上面的应用.
现在新的问题来了 2^k 该怎么求呢, 不难得出 2^k = i&(i^(i-1)); 但这个还是不好求出呀, 前辈的智慧就出来了, 2^k = i&(-i);
为什么呢?
这里利用的负数的存储特性, 负数是以补码存储的, 对于整数运算 x&(-x)有
● 当 x 为 0 时, 即 0 & 0, 结果为 0;
●当 x 为奇数时, 最后一个比特位为 1, 取反加 1 没有进位, 故 x 和 - x 除最后一位外前面的位正好相反, 按位与结果为 0. 结果为 1.
●当 x 为偶数, 且为 2 的 m 次方时, x 的二进制表示中只有一位是 1(从右往左的第 m+1 位), 其右边有 m 位 0, 故 x 取反加 1 后, 从右到左第有 m 个 0, 第 m+1 位及其左边全是 1. 这样, x& (-x) 得到的就是 x.
●当 x 为偶数, 却不为 2 的 m 次方的形式时, 可以写作 x= y * (2^k). 其中, y 的最低位为 1. 实际上就是把 x 用一个奇数左移 k 位来表示. 这时, x 的二进制表示最右边有 k 个 0, 从右往左第 k+1 位为 1. 当对 x 取反时, 最右边的 k 位 0 变成 1, 第 k+1 位变为 0; 再加 1, 最右边的 k 位就又变成了 0, 第 k+1 位因为进位的关系变成了 1. 左边的位因为没有进位, 正好和 x 原来对应的位上的值相反. 二者按位与, 得到: 第 k+1 位上为 1, 左边右边都为 0. 结果为 2^k.
总结一下: x&(-x), 当 x 为 0 时结果为 0;x 为奇数时, 结果为 1;x 为偶数时, 结果为 x 中 2 的最大次方的因子.
而且这个有一个专门的称呼, 叫做 lowbit, 即取 2^k.
二, 如何建立树状数组
上面已经解释了如何用树状数组求区间和, 那么如果我们要更新某一个点的值呢, 还是一样的, 上面说了 C[i] = A[i - 2k+1] + A[i - 2k+2] + ... + A[i], 那么如果我们更新某个 A[i]的值, 则会影响到所有包含有 A[i]位置. 如果求 A[i]包含哪些位置里呢, 同理有
A[i] 包含于 C[i + 2k],C[(i + 2k) + 2k]...;
好, 现在已经搞清楚了更新和求和, 就可以来建树状数组了. 如果上面的求和, 更新或者 lowbit 步骤还没搞懂的化, 建议再思考弄懂再往下看.
那么构造一个树状数组则为
- int n;
- int a[1005],c[1005]; // 对应原数组和树状数组
- int lowbit(int x){
- return x&(-x);
- }
- void updata(int i,int k){ // 在 i 位置加上 k
- while(i <= n){
- c[i] += k;
- i += lowbit(i);
- }
- }
- int getsum(int i){ // 求 A[1 - i]的和
- int res = 0;
- while(i> 0){
- res += c[i];
- i -= lowbit(i);
- }
- return res;
- }
这样就构造了一个树状数组. 下面看一道模板题目吧.
题目链接: https://vjudge.NET/problem/HDU-1166
直接看代码吧
- #include <bits/stdc++.h>
- using namespace std;
- int n,m;
- int a[50005],c[50005]; // 对应原数组和树状数组
- int lowbit(int x){
- return x&(-x);
- }
- void updata(int i,int k){ // 在 i 位置加上 k
- while(i <= n){
- c[i] += k;
- i += lowbit(i);
- }
- }
- int getsum(int i){ // 求 A[1 - i]的和
- int res = 0;
- while(i> 0){
- res += c[i];
- i -= lowbit(i);
- }
- return res;
- }
- int main(){
- int t;
- cin>>t;
- for(int tot = 1; tot <= t; tot++){
- cout <<"Case" << tot << ":" << endl;
- memset(a, 0, sizeof a);
- memset(c, 0, sizeof c);
- cin>>n;
- for(int i = 1; i <= n; i++){
- cin>>a[i];
- updata(i,a[i]); // 输入初值的时候, 也相当于更新了值
- }
- string s;
- int x,y;
- while(cin>>s && s[0] != 'E'){
- cin>>x>>y;
- if(s[0] == 'Q'){ // 求和操作
- int sum = getsum(y) - getsum(x-1); //x-y 区间和也就等于 1-y 区间和减去 1-(x-1)区间和
- cout <<sum << endl;
- }
- else if(s[0] == 'A'){
- updata(x,y);
- }
- else if(s[0] == 'S'){
- updata(x,-y); // 减去操作, 即为加上相反数
- }
- }
- }
- return 0;
- }
这就是最简单的点更新区间求和了.
三, 树状数组的几种变式(区间更新, 区间查询)
上面介绍的是最普通的单点更新, 区间查询, 但如果有些时候是区间更新, 单点求和怎么半, 又或是区间更新, 区间求和怎么办. 这里将介绍各种情况该怎么写.
如果上面的单点更新, 区间查询还没看懂, 建议再思考再往下看.
1. 单点更新, 单点查询
传统数组可做
2. 单点更新, 区间查询
已讲解, 详细看上面
3. 区间更新, 单点查询
这就是第一个问题, 如果题目是让你把 x-y 区间内的所有值全部加上 k 或者减去 k, 然后查询操作是问某个点的值, 这种时候该怎么做呢. 如果是像上面的树状数组来说, 就必须把 x-y 区间内每个值都更新, 这样的复杂度肯定是不行的, 这个时候, 就不能再用数据的值建树了, 这里我们引入差分, 利用差分建树.
假设我们规定 A[0] = 0;
则有 A[i] = Σij = 1D[j];(D[j] = A[j] - A[j-1]), 即前面 i 项的差值和, 这个有什么用呢? 例如对于下面这个数组
- A[] = 1 2 3 5 6 9
- D[] = 1 1 1 2 1 3
如果我们把 [2,5] 区间内值加上 2, 则变成了
- A[] = 1 4 5 7 8 9
- D[] = 1 3 1 2 1 1
发现了没有, 当某个区间 [x,y] 值改变了, 区间内的差值是不变的, 只有 D[x]和 D[y+1]的值发生改变, 至于为什么我想我就不用解释了吧.
所以我们就可以利用这个性质对 D[]数组建立树状数组, 代码为:
- int n,m;
- int a[50005] = {0},c[50005]; // 对应原数组和树状数组
- int lowbit(int x){
- return x&(-x);
- }
- void updata(int i,int k){ // 在 i 位置加上 k
- while(i <= n){
- c[i] += k;
- i += lowbit(i);
- }
- }
- int getsum(int i){ // 求 D[1 - i]的和, 即 A[i]值
- int res = 0;
- while(i> 0){
- res += c[i];
- i -= lowbit(i);
- }
- return res;
- }
- int main(){
- cin>>n;27 for(int i = 1; i <= n; i++){
- cin>>a[i];
- updata(i,a[i] - a[i-1]); // 输入初值的时候, 也相当于更新了值
- }
- //[x,y]区间内加上 k
- updata(x,k); //A[x] - A[x-1]增加 k
- updata(y+1,-k); //A[y+1] - A[y]减少 k
- // 查询 i 位置的值
- int sum = getsum(i);
- return 0;
- }
这样就把, 原来要更新一个区间的值变成了只需要更新两个点. 也很容易理解吧.
4. 区间更新, 区间查询
上面我们说的差值建树状数组, 得到的是某个点的值, 那如果我既要区间更新, 又要区间查询怎么办. 这里我们还是利用差分, 由上面可知
∑ni = 1A[i] = ∑ni = 1 ∑nj = 1D[j];
则 A[1]+A[2]+...+A[n]
- = (D[1]) + (D[1]+D[2]) + ... + (D[1]+D[2]+...+D[n])
- = n*D[1] + (n-1)*D[2] +... +D[n]
- = n * (D[1]+D[2]+...+D[n]) - (0*D[1]+1*D[2]+...+(n-1)*D[n])
所以上式可以变为∑ni = 1A[i] = n*∑ni = 1D[i] - ∑ni = 1( D[i]*(i-1) );
如果你理解前面的都比较轻松的话, 这里也就知道要干嘛了, 维护两个数状数组, sum1[i] = D[i],sum2[i] = D[i]*(i-1);
- int n,m;
- int a[50005] = {0};
- int sum1[50005]; //(D[1] + D[2] + ... + D[n])
- int sum2[50005]; //(1*D[1] + 2*D[2] + ... + n*D[n])
- int lowbit(int x){
- return x&(-x);
- }
- void updata(int i,int k){
- int x = i; // 因为 x 不变, 所以得先保存 i 值
- while(i <= n){
- sum1[i] += k;
- sum2[i] += k * (x-1);
- i += lowbit(i);
- }
- }
- int getsum(int i){ // 求前缀和
- int res = 0, x = i;
- while(i> 0){
- res += x * sum1[i] - sum2[i];
- i -= lowbit(i);
- }
- return res;
- }
- int main(){
- cin>>n;
- for(int i = 1; i <= n; i++){
- cin>>a[i];
- updata(i,a[i] - a[i-1]); // 输入初值的时候, 也相当于更新了值
- }
- //[x,y]区间内加上 k
- updata(x,k); //A[x] - A[x-1]增加 k
- updata(y+1,-k); //A[y+1] - A[y]减少 k
- // 求 [x,y] 区间和
- int sum = getsum(y) - getsum(x-1);
- return 0;
- }
再附赠两道模板题目, 可以自行写一下以便理解
区间修改, 单点查询模板题目: https://www.luogu.org/problem/show?pid=3368
区间修改, 区间查询模板题目: https://vjudge.NET/problem/POJ-3468
PS: 这里大致归纳了一维树状数组的所有要使用到的东西, 二维建树以及更多变式就不说了, 具体问题再具体分析.
后记: 自己看了一下写的不是很好, 特别是公式和图, 都是用简单的画图和直接写的, 没有用编辑器, 也不能说我懒吧, 毕竟精力有限啦, 以后有空还是会去学的, 带给大家更好的博客. 手敲也不易, 希望大家理解, 多多支持.
不懂问我噢 = =
来源: https://www.cnblogs.com/xenny/p/9739600.html