树状数组

描述

参考资料:我是传送门

  1. 一维树状数组的差分写法
  2. 二维树状数组

注意要差分处理

一维树状数组

(1). 单点修改+区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 给位置p增加x
void add(int p,int x)
{
while(p <= n)
sum[p] += x,p += p&(-p);
}
// 求位置p的前缀和
int ask(int p)
{
int res = 0;
while(p)
res += sum[p],p -= p&(-p);
return res;
}
// 区间求和
int range_ask(int l,int r)
{
return ask(r)-ask(l-1);
}

(2). 区间修改+单点查询

应用“差分”将问题转化

详情看顶端博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void add(int p,int x)
{
while(p <= n)
sum[p] += x,p += p&(-p);
}
// 给区间[l,r]加上x
void range_add(int l,int r,int x)
{
add(l,x),add(r+1,-x);
}
int ask(int p)
{
int res = 0;
while(p)
res += sum[p],p -= p&(-p);
return res;
}

(3). 区间修改+区间查询

继续“差分”

无论是时间上还是空间上都比带$lazy$标记的线段树要优

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void add(ll p,ll x)
{
for(int i = p;i <= n;i += i&(-i))
sum1[i] += x,sum2[i] += x*p;
}

void range_add(ll l,ll r,ll x)
{
add(l,x),add(r+1,-x);
}
ll ask(ll p)
{
ll res = 0;
for(int i = p;i;i -= i&(-i))
res += (p+1)*sum1[i]-sum2[i];
return res;
}
ll range_ask(ll l,ll r)
{
return ask(r)-ask(l-1);
}

二维树状数组

$tree[x][y]$ : 记录右下角为$(x,y)$,高为lowbit(x),宽为lowbit(y)的区间的区间和

(1). 单点修改+区间查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void add(int x,int y,int z)
{
int memo_y = y;
while(x <= n)
{
y = memo_y;
while(y <= m)
tree[x][y] += z,y += y&(-y);
x += x&(-x);
}
}
// 求左上角为(1,1)右下角为(x,y)的矩阵和
void ask(int x,int y)
{
int res = 0,memo_y = y;
while(x)
{
y = memo_y;
while(y)
res += tree[x][y],y -= y&(-y);
x -= x&(-x);
}
}

ll range_ask(ll xa, ll ya, ll xb, ll yb)
{
return ask(xb,yb) - ask(xb,ya - 1) - ask(xa - 1,yb) + ask(xa - 1,ya - 1);
}

(2). 区间修改+单点查询

我们对于一维数组进行差分,是为了使差分数组前缀和等于原数组对应位置的元素。

那么如何对二维数组进行差分呢?可以针对二维前缀和的求法来设计方案。

二维前缀和:

$sum[i][j]=sum[i−1][j]+sum[i][j−1]−sum[i−1][j−1]+a[i][j]$

那么我们可以令差分数组$d[i][j]$ 表示 $a[i][j]$ 与 $a[i−1][j]+a[i][j−1]−a[i−1][j−1]$ 的差。

例如下面这个矩阵

1
2
3
1  4  8
6 7 2
3 9 5

对应的差分数组就是

1
2
3
 1  3  4
5 -2 -9
-3 5 1

当我们想要将一个矩阵加上x时,怎么做呢?
下面是给最中间的3*3矩阵加上x时,差分数组的变化:

1
2
3
4
5
0  0  0  0  0
0 +x 0 0 -x
0 0 0 0 0
0 0 0 0 0
0 -x 0 0 +x

这样给修改差分,造成的效果就是:

1
2
3
4
5
0  0  0  0  0
0 x x x 0
0 x x x 0
0 x x x 0
0 0 0 0 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void add(int x,int y,int z)
{
int memo_y = y;
while(x <= n)
{
y = memo_y;
while(y <= m)
tree[x][y] += z,y += y&(-y);
x += x&(-x);
}
}

void range_add(int xa,int ya,int xb,int yb,int z)
{
add(xa,ya,z);
add(xa,yb+1,-z);
add(xb+1,ya,-z);
add(xb+1,yb+1,z);
}

int ask(int x,int y)
{
int res = 0,memo_y = y;
while(x)
{
y = memo_y;
while(y)
res += tree[x][y],y -= y&(-y);
x -= x&(-x);
}
return res;
}

(3). 区间修改+区间查询

四个树状数组,分别维护

$d[i][j], d[i][j]∗i, d[i][j]∗j, d[i][j]∗i∗j$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int N = 205;
ll n,m,Q;
ll t1[N][N],t2[N][N],t3[N][N],t4[N][N];
void add(ll x,ll y,ll z)
{
for(int X = x;X <= n;X += X&(-X))
for(int Y = y;Y <= m;Y += Y&(-Y))
{
t1[X][Y] += z;
t2[X][Y] += z*x;
t3[X][Y] += z*y;
t4[X][Y] += z*x*y;
}
}

void range_add(ll xa,ll ya,ll xb,ll yb,ll z)
{
add(xa,ya,z);
add(xa,yb+1,-z);
add(xb+1,ya,-z);
add(xb+1,yb+1,z);
}

ll ask(ll x,ll y)
{
ll res = 0;
for(int i = x;i;i -= i&(-i))
for(int j = y;j;j -= j&(-j))
res += (x+1)*(y+1)*t1[i][j]
- (y+1)*t2[i][j] - (x+1)*t3[i][j]
+ t4[i][j];
return res;
}

ll range_ask(ll xa,ll ya,ll xb,ll yb)
{
return ask(xb,yb) - ask(xb,ya-1) - ask(xa-1,yb)
+ ask(xa-1,ya-1);
}