数据结构树状数组（三）

学习笔记-树状数组（三）

树状数组（一）

树状数组（二）

通过树状数组的基本操作，我们可以实现区间查询和单点修改。结合差分，又可以实现单点查询和区间修改。那么，怎么才能像线段树一样，快速实现区间查询，区间修改呢？

由差分到前缀和

既然要区间修改，那么一定要使用差分数组而不是原始数组

由上一篇可见，c₁+c₂+...+c_i=a_i

也就是说，差分数组的前缀和=原数值

而原数值的前缀和=前缀和

所以前缀和=差分数组的前缀和的前缀和

虽然听起来有点绕，但是结论是这样

简单尝试推导

那么，可以推出如下算式

a₁+a₂+a₃+...+a_i

=(c₁)+(c₁+c₂)+(c₁+c₂+c₃)+...+(c₁+c₂+...+c_i)

=c₁*(i)+c₂*(i-1)+c₃*(i-2)+...+c_i-1*2+c_i*1

可以看出来，差分数组的第j个数会被加i-j+1次

...然而貌似还是很不方便

进一步推导

运用一些简单的数学知识（这块我也讲不明白），最后推导完毕的式子是这样：

a₁+a₂+...+a_i

=(i+1)*(c₁+c₂+...+c_i)-(c₁*1+c₂*2+...+c_i*i) ——如果你不想写线段树，请牢记这个推导式

经过各种玄学等式变形，我们得到了这样一个算式，可以保证差分数组的第i个数被加i遍。

这样，只要建立两个差分数组的树状数组，一个存储ci、一个存储ci*i，就可以区间修改查询了。

结论（画重点）

为了方便调用，我们把树状数组建成二维tree[0][i]表示c_i，tree[1][i]表示c_i*i

那么在使用单点修改函数对差分数组单点修改时，要在tree_0,i加k，在tree_1,i加i*k

想要查询前缀和时，就可以计算(i+1)*(tree_0,i的前缀和)-(tree_1,i的前缀和)

程序实现

区间修改

我们在基础程序上加一维f，作为区分c_i和c_i*i两数组的变量

1 void add(int x,int k,bool f)
2 {
3     while(x<=n)
4     {
5         tree[f][x]+=k;
6         x+=lowbit(x);
7     }
8 }

然后把它套在前面加粗的那个斜体结论上

1 void update(int x, int k)
2 {
3     add(x, k, 0);
4     add(x, x*k, 1);
5 }

这就是完整的对差分数组单点修改函数

那么，使用差分数组的O(1)修改的特点，在主程序里进行两次update操作，就可以完成区间修改

比如要对x到y加上k，就可以这样

update(x, k);
update(y+1, -k);

区间查询

和区间修改的变化一样的步骤，首先添加维度

1 int sch(int x, bool f){
2     int ans = 0;
3     while(x >= 1){
4         ans += tree[f][x];
5         x -= lowbit(x);
6     }
7     return ans;
8 }

然后套用结论

1 int sum(int x)
2 {
3     int ans = (x + 1) * (sch(x, 0)) - sch(x, 1);
4     return ans;
5 }

最后，利用前缀和数组的O(1)查询的特点，在主程序里面调用两次sum，就可以了

比如要求出x到y的区间和，赋值给res，就可以这样

res = sum(y) - sum(x - 1);

例题

LGOJ-P3372

题目大意

实现区间修改和查询

输入输出格式

输入格式：

第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。

第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。

接下来M行每行包含3或4个整数，表示一个操作，具体如下：

操作1：格式：1 x y k 含义：将区间[x,y]内每个数加上k

操作2：格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：

输出包含若干行整数，即为所有操作2的结果。

程序实现

 1 #include<cstdio>
 2 #include<cctype>
 3 #define ll long long
 4 using namespace std;
 5 ll n, m, tree[2][100010];
 6 inline ll read(){
 7     char ch = getchar();
 8     ll f = 1, x = 0;
 9     while(!isdigit(ch)){
10         if(ch == '-') f = -1;
11         ch = getchar();
12     }
13     while(isdigit(ch)){
14         x *= 10;
15         x += (ch & 15);
16         ch = getchar();
17     }
18     return f * x;
19 }
20 ll lowbit(ll x){
21     return x & (-x);
22 }
23 void add(ll x,ll k,ll f)
24 {
25     while(x<=n)
26     {
27         tree[f][x]+=k;
28         x+=lowbit(x);
29     }
30 }
31 void update(ll x, ll k)
32 {
33     add(x, k, 0);
34     add(x, x*k, 1);
35 }
36 ll sch(ll x, ll f){
37     ll ans = 0;
38     while(x >= 1){
39         ans += tree[f][x];
40         x -= lowbit(x);
41     }
42     return ans;
43 }
44 ll sum(int x)
45 {
46     ll ans = (x + 1) * (sch(x, 0)) - sch(x, 1);
47     return ans;
48 }
49 int main(){
50     n = read(), m = read();
51     for(ll i = 1, a = 0, b = 0; i <= n; i++){
52         b = read();
53         update(i, b - a);
54         a = b;
55     }
56     while(m--){
57         if(read() == 1){
58             ll x, y, z;
59             x = read(); y = read(); z = read();
60             update(x, z); update(y + 1, -z);
61         }
62         else{
63             ll x, y;
64             x = read(); y = read();
65             printf("%lld\n", (sum(y) - sum(x - 1)));
66         }
67     }
68     return 0;
69 }