Binary Indexed Trees(树状数组)

1.lowbit

lowbit(x)是x的二进制表达式中最低位的1所对应的值。比如,6的二进制是110,所以lowbit(6)=2。

lowbit(x) = x&(-x)

2.定义,查询，修改(eg1)

$a1,a2,...,an$

能在BZ的时间复杂度下完成：

单点加，$ai+=d$
查询前缀和$\sum_{i = 1}^{x}ai$

树状数组定义：

$c_i = a_{i-lowbit(i)+1到i}$的和

画个图...

修改和查询：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;

int a[N],n;
ll c[N];
ll query(int x){//1...x
	ll s = 0;
	for(;x;x-=x&(-x))
		s += c[x];
	return s;
}
void modify(int x,ll s){//a[x]+=s
	for(;x<=n;x+=x&(-x))
		c[x]+=s;
}

例题1.树状数组1

给n个数a1,a2,a3,…,an。

支持q个操作：

1 x d，修改$ax=d$。
2 x，查询$\sum_{i=1}^{x}ai$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
int n,q;
int a[N];
ll c[N];
ll query(int x){//1...x
	ll s = 0;
	for(;x;x-=x&(-x))
		s += c[x];
	return s;
}
void modify(int x,ll s){//a[x]+=s
	for(;x<=n;x+=x&(-x))
		c[x]+=s;
}

int main()
{
	cin>>n>>q;
	for(int i = 1;i<=n;i++)
	{
		cin>>a[i];
		modify(i,a[i]);
	}
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,d;
			cin>>x>>d;
			modify(x,d-a[x]);
			a[x] = d;
		}
		else
		{
			int x;
			cin>>x;
			cout<<query(x)<<endl;
		}
	}
	return 0;
}

3.应用(eg2,3)

eg2.逆序对2

请问数组 $a$ 的逆序对一共有多少个？形式化的说，请求出有多少组$ (i,j)$满足$ i<j$ 并且 $ai>aj$。

思路：

扫描线思想，静态=>动态

for(j = 1~n)

统计$a_1$~$a_{j-1}$里面有多少个>$a_j$的

我们有一个数据结构D，D里面存了$a_1$~$a_{j-1}$。

问题变成了我们要统计D里面有多少个$>=a_j$的，统计完之后，我们把$a_j$加入D中。我们再动态的过程中不断把答案加起来，就是所有的逆序对数了。

我们把一个静态的问题转化为一个动态带修改的问题。
对权值开树状数组

对D里面，我们要做的是a.加入一个数 b.查询有多少个$>=a_j$的数

比如我们加入一个数$a_i$,那我们再$D[a[i]]$位置++

要查询多少个$>=a_j$的数，即查询$a_j$后面又多少个1,实际上是做一个后缀查询。$for(i = a_{j+1}$~$n)ans += D[i]$

总结：

①D[a[j]]+=1

②后缀查询

这里跟树状数组没什么区别了，唯一区别就是前缀查询变成了后缀，我们把所有东西翻过来，就变成前缀和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
int n;
int a[N];
ll c[N];
ll query(int x){//1...x
	ll s = 0;
	for(;x;x-=x&(-x))
		s += c[x];
	return s;
}
void modify(int x,ll s){//a[x]+=s
	for(;x<=n;x+=x&(-x))
		c[x]+=s;
}

int main()
{
	cin>>n;
	for(int i = 1;i<=n;i++)
	{
		cin>>a[i];
		a[i] = n+1-a[i];
	}
	ll ans = 0;
	for(int i = 1;i<=n;i++)
		ans += query(a[i]),modify(a[i],1);
	cout<<ans<<endl;
	return 0;
}

eg3.树状数组2

有$n$个数$a1,a2,a3,…,an$一开始都是0。

支持$q$个操作：

1 l r d，令所有的$a_i(l≤i≤r)$加上$d$。
2 x，查询$(\sum_{i=1}^{x}ai) \bmod 2^{64}$。

操作：区间加+单点查询

差分：$d_i = a_i - a_{i-1}$

前缀和：$a_i = d_1+d_2...+d_i$

$[l,r]+1$

$d_l+=1,d_{r+1}-=1$

查询单点其实就是个d的前缀和$\sum_{i = 1}^{x}a_i$

$a_1 = d_1$

$a_2 = d_1+d_2$

$a_3 = d_1+d_2+d_3$

那么$a_1+a_2+a+3 = 3d_1+2d_2+d_3$

那么$a_x = xd_1+(x-1)d_2+...+d_x = \sum_{i = 1}^{x}(x+1-i)*d_i $

化简一下$(x+1)(\sum_{i = 1}^{x}d_i)-(\sum_{i = 1}^{x}i*d_i) $

那么我们只需要维护出$d_i$的前缀和和$i*d_i$的前缀和就行了。这两个东西我们开两个树状数组取维护它。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long u64;
const int N = 201000;
int n,q;
int a[N];
template<class T>
struct BIT
{
	T c[N];
	int size;
	void resize(int s){size = s;}
	T query(int x){//1...x
		assert(x<=size);
		T s = 0;
		for(;x;x-=x&(-x))
			s += c[x];
		return s;
	}
	void modify(int x,T s){//a[x]+=s
		assert(x!=0);//注意：树状数组下标不能是0，因为lowbit会死循环
		for(;x<=n;x+=x&(-x))
			c[x]+=s;
	}

};
BIT<u64>c1,c2;//c1:d[i],c2:i*d[i]

int main()
{
	cin>>n>>q;
	c1.resize(n),c2.resize(n);
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int l,r;
			u64 d;
			cin>>l>>r>>d;
			c1.modify(l,d);
			c1.modify(r+1,-d);
			c2.modify(l,l*d);
			c2.modify(r+1,(r+1)*(-d));
		}
		else
		{
			int x;
			cin>>x;
			u64 ans = (x+1)*c1.query(x)-c2.query(x);
			cout<<ans<<endl;
		}
	}
	return 0;
}

4.二分(eg4)

给$n$个数$a1,a2,a3,…,an。$

支持q个操作：

1 x d，修改$a_x=d$。
2 s，查询最大的$T(0≤T≤n)$满足$\sum_{i=1}^{T}ai≤s$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 201000;
int n,q;
int a[N];
ll c[N];
/*
写法1：
ll query(ll s){
	ll t = 0;
	int pos = 0;

		// for(j = log(n)~0)
		// pos 是当前的位置
		// t 记录的是1~pos的和
		// pos' = pos+2^j

	for(int j = 18;j>=0;j--)
	{
		if(pos+(1<<j)<=n&&t+c[pos+(1<<j)]<=s)
		{
			pos += (1<<j);
			t+=c[pos];
		}
	}
	return pos;
}
*/
//写法2：
ll query(ll s){
	int pos = 0;
	for(int j = 18;j>=0;j--)
	{
		if(pos+(1<<j)<=n&&c[pos+(1<<j)]<=s)
		{
			pos += (1<<j);
			s-=c[pos];
		}
	}
	return pos;
}

void modify(int x,ll s){//a[x]+=s
	for(;x<=n;x+=x&(-x))
		c[x]+=s;
}

int main()
{
	cin>>n>>q;
	for(int i = 1;i<=n;i++)
	{
		cin>>a[i];
		modify(i,a[i]);
	}
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,d;
			cin>>x>>d;
			modify(x,d-a[x]);
			a[x] = d;
		}
		else
		{
			ll s;
			cin>>s;
			cout<<query(s)<<endl;
		}
	}
	return 0;
}

5.高维树状数组(eg5)

$c[i][j]$

$a[i-lowbit[i]+1$~$i]$ $[j-lowbit[j]+1$~$j]$

eg5.二维树状数组

给$n×m$个数$a_{1,1},a_{1,2},a_{1,3},…,a_{1,m},…,a_{n,m}$。

支持$q$个操作：

1 x y d，修改$a_{x,y}=d$。

2 x y，查询$\sum_{i = 1}^{x}a_{i,j}$。

时间复杂度$O(log^2(n))$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 510;
int n,m,q;
int a[N][N];
ll c[N][N];
ll query(int x,int y){
	ll s = 0;
	for(int p = x;p;p-=p&(-p))
		for(int q = y;q;q-=q&(-q))
			s += c[p][q];
	return s;
}

void modify(int x,int y,ll s){
	for(int p = x;p<=n;p+=p&(-p))
		for(int q = y;q<=m;q+=q&(-q))
			c[p][q]+=s;
}

int main()
{
	cin>>n>>m>>q;
	for(int i = 1;i<=n;i++)
	{
		for(int j = 1;j<=m;j++)
		{
			cin>>a[i][j];
			modify(i,j,a[i][j]);
		}
	}
	for(int i = 1;i<=q;i++)
	{
		int op;
		cin>>op;
		if(op==1)
		{
			int x,y,d;
			cin>>x>>y>>d;
			modify(x,y,d-a[x][y]);
			a[x][y] = d;
		}
		else
		{
			int x,y;
			cin>>x>>y;
			cout<<query(x,y)<<endl;
		}
	}
	return 0;
}