数据结构-树状数组

一、前言

感觉时间有点不太够了(整日摸鱼= =)，打算简单内容就不说了模板直接丢在这里，多记一些应用方面的东西qwq

二、模板

#define Lof(i,a,b) for(Re int i=(a),_=(b);i<=_;i+=i&-i)
#define Lor(i,a) for(Re int i=(a);i;i-=i&-i)
struct BIT{//一维
	int da[N];
	void clear() {Ms(da,0);}
	void Modify(int x,int d) {Lof(i,x,n)da[x]+=d;}
	int query(int x) {int t=0;Lor(i,x)t+=da[x];return t;}
}T;

struct TDBIT{//二维
	int da[N][N][N];
	void clear() {Ms(da,0);}
	void Modify(int p,int x,int y,int d) { Lof(i,x,n) Lof(j,y,m) da[p][i][j]+=d;}
	int qry(int p,int x,int y) {int t=0;Lor(i,x) Lor(j,y) t+=da[p][i][j];return t;}
	int query(int p,int x1,int y1,int x2,int y2) {return qry(p,x2,y2)+qry(p,x1-1,y1-1)-qry(p,x1-1,y2)-qry(p,x2,y1-1);}
}T;

三、应用

树状数组的应用多种多样，这里持续总结吧~

3.1 区间修改与求和

现有原数组a[]，b[]为a[]的标记差分数组(初始是0，只记录修改变化)。区间[l,r]都+x即为b[l]+=x,b[r+1]-=c。

区间[l,r]求和即为sum(1,r)-sum(1,l)，即只需求前缀和。

修改后第i项的值为(a[i]+sum_{j=1}^ib[j]) ，那么(sum(1,r)=sum_{i=1}^r(a[i]+b[i]*(r-i+1)))

化简后为(sum(1,r)=sum_{i=1}^ra[i]+(r+1)sum_{i=1}^rb[i]-sum_{i=1}^r(b[i]*i)) 第一项直接前缀和，后两项用树状数组维护即可

另外和这个方法类似可推导出二维情况的式子，但需要维护4个二维树状数组= =

3.2nlogn求逆序对

将原数列离散化后一个一个插入统计和当前数逆序的数字有多少。

3.3求LIS

就维护小于等于i的长度最大值= =

PS:想不到了(阿巴阿巴0.0)，就先写到这吧遇上题再补充~