树状数组基础知识以及相关习题

什么是树状数组？

 和并查集一样，树状数组和线段树都是算法竞赛中常见的数据结构，他们通常结构清晰，操作方便，应用灵活，效率很高。

如何理解树状数组

• 一句话概括：树状数组可以高效率的查询和维护前缀和（或区间和）

 所谓前缀和，即给出长度为n的数列A={$a_1,a_2,a_3,....,a_x$}和一个查询$x<=n$，求$sum(x)=a_1+a_2+\dots +a_x$。数列$[i，j]$区间和通过前缀和求得，即ai+…+aj=sum(j)-sum(i-1)。
 如果数列A是静态不变的，代码很好写，预处理前缀和就好了，一次预处理的复杂度为0(n），然后每次查询复杂度都为O(1)。但是，如果序列是动态变化的，如改变其中一个元素a的值，那么它后面的前缀和都会改变，需要重新计算，如果每次查询前元素都有变化，那么一次查询的复杂度就变为O（n）。

如何理解精髓lowbit

lowbit(x)=x&-x,功能是找x的二进制最后一个1，原理是用到了负数的补码。下面这两张张表可能能更好的让你理解为什么树状数组这样构造，以及他的基础函数的由来

二叉树和树状数组的结构

上述图片给我们展示了二叉树到树状数组的结构变换，有助于我们更好的理解树状数组。

树状数组的优点

优点：修改和查询操作复杂度于线段树一样都是logN,但是常数比线段树小，并且实现比线段树简单

缺点：扩展性弱，线段树能解决的问题，树状数组不一定能解决.

树状数组模板

万变不离其宗，这两个函数是树状数组的精髓，要好好掌握。

void update (int x,int k) {while (x<=N) {tree[x]+=k;x+=lowbit(x);}
}
int query (int x) {int ans=0;while (x>0) {ans+=tree[x];x-=lowbit(x);}return ans;
}

关于如何理解树状数组可以结合有关资料学习，这里只给出模板，并给出一些练习题帮助更好的理解树状数组

单点修改，区间查询

const int N = 1e6+5;
int a[N],b[N];
int tree[N];
int n,m;void solve ()
{cin>>n>>m;for (int i=1;i<=n;i++) {int x;cin>>x;update(i,x);}for (int i=1;i<=m;i++) {int pos,x,y;cin>>pos>>x>>y;if(pos==1) {update(x,y);}else {cout<<query (y)-query (x-1)<<'\n';}}return ;
}

区间修改，单点查询

区间修改，单点查询的模板用到了差分数组，不懂差分的可以去查询有关资料

const int N = 1e6+5;
int a[N],b[N];
int chafen[N];
int tree[N];
int n,m;void solve ()
{cin>>n>>m;for (int i=1;i<=n;i++) {cin>>chafen[i];int x=chafen[i]-chafen[i-1];update(i,x);}for (int i=1;i<=m;i++) {int pos,x,y,k;cin>>pos;if(pos==1) {cin>>x>>y>>k;update(x,k);update(y+1,-k);}		else {cin>>x;cout<<sum(x)<<'\n';}}return ;
}

区间修改，区间查询

这部分代码有些难以实现，运用到了数学的相互转换。区间修改，区间查询是线段树的强项。我把两种方法都贴出来以供参考

树状数组法

#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e6+5;
int a[N],b[N];
int tree1[N],tree2[N];
int m,n;void update1 (int x,int k) {while (x<=n) {tree1[x]+=k;x+=lowbit(x);}
}void update2 (int x,int k) {while (x<=n) {tree2[x]+=k;x+=lowbit(x);}
}int sum1 (int x) {int res=0;while (x>0) {res+=tree1[x];x-=lowbit(x);}return res;
}int sum2 (int x) {int res=0;while (x>0) {res+=tree2[x];x-=lowbit(x);}return res;
}void solve () {cin>>m>>n;for (int i=1;i<=m;i++) {cin>>a[i];int x=a[i]-a[i-1];update1 (i,x);update2 (i,(i-1)*x);}for (int i=1;i<=n;i++) {int pos;cin>>pos;if (pos==1) {int x,y,k;cin>>x>>y>>k;update1(x,k);update1(y+1,-k);update2(x,k*(x-1));update2(y+1,-k*y);}else {int x,y;cin>>x>>y;int ans1=y*sum1(y)-sum2(y);int ans2=(x-1)*sum1(x-1)-sum2(x-1);cout<<ans1-ans2<<'\n';}}
}

线段树法

#include <bits/stdc++.h>
#define int long long 
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 1e5+5;
int a[N];
int tree [N<<2],tag[N<<2];int ls (int p) {return p<<1;}
int rs (int p) {return p<<1|1; }void push_up (int p) {tree[p]=tree[ls(p)]+tree[rs(p)];
//	tree[p]=min (tree[ls(p)],tree[rs(p)]);//Çó×îСֵµÄʱºòpush_upº¯ÊýÀïÃæÊÇÕâ¸ö 
}void build (int p,int pl,int pr) {tag[p]=0;if (pl==pr) {tree[p]=a[pl];return ;}int mid = (pl+pr)>>1;build (ls(p),pl,mid);build (rs(p),mid+1,pr);push_up(p);
}void addage (int p,int pl,int pr,int d) {tag[p] += d;tree[p] += d*(pr-pl+1);
}void push_down (int p,int pl,int pr) {if (tag [p]) {int mid = (pl+pr)>>1;addage  (ls(p),pl,mid,tag[p]);addage (rs(p),mid+1,pr,tag[p]);tag[p]=0;}
}void update (int l,int r,int p,int pl,int pr,int d) {if (l <= pl && pr <= r) {addage (p,pl,pr,d);return ;}push_down(p,pl,pr);int mid=(pl+pr)>>1;if (l <= mid) update (l,r,ls(p),pl,mid,d);if (r > mid) update (l,r,rs(p),mid+1,pr,d);push_up (p);
}int query (int l,int r,int p,int pl,int pr) {if (pl>=l&&pr<=r) return tree[p];push_down (p,pl,pr);int res=0;int mid = (pl+pr)>>1;if (l<=mid) res += query (l,r,ls(p),pl,mid);if (r>mid) res +=query (l,r,rs(p),mid+1,pr);return res; 
}void solve () {int n,m;cin>>n>>m;for(int i=1;i<=n;i++)  cin>>a[i];build (1,1,n);while (m--) {int q,l,r,d;cin>>q;if (q==1) {cin>>l>>r>>d; update (l,r,1,1,n,d);}else {cin>>l>>r;cout<<query (l,r,1,1,n)<<'\n';}}}

虽然说线段树才是这类题的正解，但是线段树代码量很大，难以实现。树状数组相较于它的优点就是代码量少。但是有些问题（当然我还没遇到）只能用线段树来解决，树状数组就显得力不从心了。

树状数组基础练习题

逆序对

来源：洛谷
这是一道利用离散化结合树状数组的例题

 一道逆序对的例题，这个例题可以用归并排序的方法写，也可以用树状数组的方法写，如果要用到树状数组来写的话，就要用到离散化，因为数据比较大。这里我们用到的方法是树状数组。
其中的核心思想就是把数字看成树状数组的下标

#include <bits/stdc++.h>
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 1e6+5;
int a[N];
int chafen[N];
int tree[N];
int n,m;struct jiegou {int x,y;
}b[N];bool cmp (jiegou qwe,jiegou asd) {if (qwe.x!=asd.x)	return qwe.x<asd.x;return qwe.y<asd.y;
}//两个基础函数void solve () {cin>>n;for (int i=1;i<=n;i++) {cin>>b[i].x;b[i].y=i;}sort (b+1,b+1+n,cmp);for (int i=1;i<=n;i++) a[i]=b[i].y;int res=0;for (int i=n;i>=1;i--) {update(a[i],1);res+=sum(a[i]-1);}cout<<res;hreturn ;
}

动态求连续区间和

来源：ACwing
模板题，直接套用模板就可以

const int N = 2e5+5;
int a[N],tree[N];int n,k;
//两个基础函数，这里省略没写
void solve () {cin>>n>>k;for (int i=1;i<=n;i++) {cin>>a[i];update (i,a[i]);}for (int i=1;i<=k;i++) {int q,x,y;cin>>q>>x>>y;if (q==1) {update (x,y);}else {cout<<query (y)-query (x-1)<<'\n';}}return;
}

数星星

来源：ACwing
画出图像就能发现，我们只用求前面有多少小于x的数即可。前面有多少个数字，那么这个输入就是几级星星。多次求前缀和，优先想到我们的树状数组。我们用一个ans数组来存放i级星星有多少个。后续直接输出就可以

//两个基础函数没有写出
void solve () {int n;cin>>n;for (int i=1;i<=n;i++) {int x,y;cin>>x>>y;x++;//这里注意下标加1，因为树状数组下标不为0ans[query (x)]++;//求x前面有多少个数字，再用ans数组存起来update (x,1);}for (int i=0;i<n;i++) cout<<ans[i]<<'\n';return;
}

校门外的树

来源：ACwing
每一个$[l,r]$里面的树都是一种，给出很多组l，r。问当查询[l,r]时，有多少种树。
其实这一题用到了一个括号序列的思想，我们把$[l,r]$中l上放置一个左括号，r上放置一个右括号。在这一个括号里面树都是一种。这样我们只用维护括号的数量，最后查询括号的数量即可。
怎么查询$[l,r]$里面有多少种树？我们画图就能发现。我们把r之前的左括号减去i之前的右括号即可。
故用两个树状数组分别维护左右括号的前缀和，更新时记录左右括号数，查询时相减即能得到结果

void solve () {int n,k;cin>>n>>k;for (int i=1;i<=k;i++) {int q,x,y;cin>>q>>x>>y;if (q==1) {update1 (x,1);update2 (y,1);}else {cout<<query1 (y) - query2 (x-1) << '\n';}}
}

巧妙的将求树的种类转化成求括号的数量

简单题

来源：ACwing
和上一题差不多，但这一题是反转0,1序列。我们依然用括号的思想，$[l,r]$里反转，我们就在两边加括号，单点查询的时候，我们就查询这个点被多少个括号扩了起来，就反转了几下，然后只能是0,1的缘故，我们直接判断奇偶就行了。
多点修改，单点查询，十分符合树状数组，直接开写。
实际上就是找这一点（包括这一点）之前左括号与右括号的差值

void solve () {int n,k;cin>>n>>k;for (int i=1;i<=k;i++) {int q,x,y;cin>>q;if (q==1) {cin>>x>>y;update1 (x,1);update2 (y,1);}else {cin>>x;int q = query1 (x) - query1 (x-1);
//			int w = query2 (x) - query2 (x-1); int pos = query1 (x-1) - query2 (x-1);pos += q;if (pos%2==0) cout<<"0"<<'\n';else cout<<"1"<<'\n';}}
}

打鼹鼠

来源：ACwing
这是一道二维树状数组的练习题，也是属于的一道板子题，可以看一看，就是将一维改成二维。

const int N=1040;
int c[N][N], n;void update (int x, int y, int k) {for(int i=x; i<=N; i+=lowbit(i)){for(int j=y; j<=N; j+=lowbit(j)){c[i][j] += k;}}
}int query (int x, int y){int ans = 0;for(int i=x; i>=1; i-=lowbit(i))for(int j=y; j>=1; j-=lowbit(j))ans += c[i][j];return ans;
}void solve () {cin>>n;int xx, yy, x, y, k, op;while(cin>>op, op!=3) {if(op==1){cin>>x>>y>>k;update(x+1, y+1, k);}else{cin>>x>>y>>xx>>yy;xx++, yy++;cout<<query (xx,yy)-query (xx,y)-query (x,yy)+query (x,y)<<'\n';}}
}