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;
}