关于树状数组区间修改和查询详解

心已赠人 2022-06-13 01:28 178阅读 0赞

[原版介绍][Link 1]  
这里我想再加上自己的理解，解释一下。  
现在我们需要的是把某个区间的值修改，然后查询  
我们设原数组为  
**a\[1\] a\[2\] …. a\[n\]**  
我们添加一个**c1数组 来记录此项与前一项的差值** 即  
**c1\[i\] = a\[i\] - a\[i-1\]**  
再添加上c2数组，根据公式**c1与c2的关系**（下面会说到）  
**c2\[i\] = (i-1)\*(a\[i\] - a\[i-1\])**  
下面是推导过程：

a\[1\]+a\[2\]+…+a\[n\]

= (c\[1\]) + (c\[1\]+c\[2\]) + … + (c\[1\]+c\[2\]+…+c\[n\])

= n \* c\[1\] + (n-1) \* c\[2\] +… +c\[n\]

= n \* (c\[1\]+c\[2\]+…+c\[n\]) - (0 \* c\[1\]+1\* c\[2\]+…+(n-1) \* c\[n\]) ①

这就是三者之间关系，根据规律，提取公式

**0 \* c\[1\] + 1\* c\[2\] + … + (n-1) \* c\[n\]** →用c2记录 → **c2\[i\] = (i-1)\*c\[i\]**

根据①式，我们得出

**原式 = n\*sigma(c1, n) - sigma(c2, n)** //sigma（c1, n）代表c1数组的前n项和

**这里才能体现出c2的作用** → 帮助更好的计算

这样前提工作做好了

首先第一个要求是把区间 **\[left，right\]** 内所有的数加上 **x**  
这里我们写一个和单个修改类似的函数**add**

void add(ll *a, ll pos, ll x) {
        while( pos <= n ) {
            a[pos] += x;
            pos += lowbit(pos);
        }
    }

通过这个函数，其实是把从 **left** 开始以后的数全都加上了 **x** 所以需要减掉 **right** 以后的数

add(c1, left, x); 
    add(c1, right+1, -x);

由于c1数组变化了，所以c2数组也要变化

add(c2, left, (left-1)*x); //更新标记数组 
    add(c2, right+1, -right*x); //把多余的去掉

同样还是需要减去多加的数字

这样的话就已经完成了修改，只需要把sigma函数写出来输出就可以了  
这只是其中一种做法  
下面是一个模板例题  
例题：[线段树练习][Link 2]

代码如下：

#include<cstdio>
    #include<iostream>
    #define lowbit(x) x&(-x)
    #define maxn 200010
    #define ll long long
    using namespace std;
    ll n; 
    ll a[maxn];//原数组 
    ll c1[maxn];//差值数组 
    ll c2[maxn];//根据差值数组根据关系推得的一组数据 起名为标记数组 
    ll sigma(ll *a, ll pos) {
        ll sum = 0;
        while(pos > 0) {
            sum += a[pos];
            pos -= lowbit(pos);
        }
        return sum;
    }
    void add(ll *a, ll pos, ll x) {
        while( pos <= n ) {
            a[pos] += x;
            pos += lowbit(pos);
        }
    }
    int main() {
        cin >> n;
        for(ll i = 1; i <= n; i++) {
            cin >> a[i];
            add(c1, i, a[i] - a[i-1]); //把该项与前一项的差值记录下来 
            add(c2, i, (i-1)*(a[i] - a[i-1])); //根据公式来更新标记数组 
        }
        ll t;
        cin >> t;
        while( t-- ) {
            ll index, left, right, x;
            cin >> index;
            if(index == 1) {
                cin >> left >> right >> x;
                add(c1, left, x); //更新数组 
                add(c1, right+1, -x); //由于前面更新过，把多余的减去 
                add(c2, left, (left-1)*x); //更新标记数组 
                add(c2, right+1, -right*x); //把多余的去掉 
            }  //右边界都要去掉，因为到该项结束，但是不能修改 
    
            if(index == 2) {
                cin >> left >> right;
                ll sum1 = (left-1)*sigma(c1, (left-1)) - sigma(c2, (left-1));//公式 
                ll sum2 = right*sigma(c1, right) - sigma(c2, right);
                cout << sum2 - sum1 << endl;
            }
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/fsahfgsadhsakndas/article/details/52650026
[Link 2]: http://codevs.cn/problem/1082/