简单理解一维树状数组区间求和+修改

FBI WARNING

在阅读前，请先弄懂单点修改+区间查询和区间修改+单点查询。

近日，本萌新在学习了树状数组后，在某度上寻找了各大大佬的区间修改+区间查询的博客，里面会有诸如此类：

以及

的操作...

（高一萌新瑟瑟发抖..）

于是乎，在我的不懈努力（手动模拟）之下，终于弄懂了这个树状数组区间求和修改的奥♂义。

那么首先我们假设一个数组a，里面是我们的所有数。

让我们回忆一下区间修改需要干什么，对了！维护差分数组！

所以我们再来一个数组d，是我们数组a的差分数组。

所以a[i] = d[1] + d[2] + .. + d[i]; (下标从一开始)

因此我们只需要维护一个差分数组就可以了。

让我们再回忆一下区间查询该怎么做，对了！前缀和！

那么肯定有人要问了，我堂堂正正一个差分数组，前缀和怎么搞？

现在我们来看一下：

• a[1] = d[1];

• a[2] = d[1] + d[2];

• a[3] = d[1] + d[2] + d[3];

• a[4] = d[1] + d[2] + d[3] + d[4];

停！打住！够了。

假设我们要求sum[4] = a[1] + a[2] + a[3] + a[4]。

那么我们的式子就会变成;

sum[4] = d[1] + d[1] + d[2] + d[1] + d[2] + ........ + d[4];

超麻烦啊喂！

我们回去再看一看a[1] - a[4]那四行。这次我们竖着看。

有没有豁然开朗的赶脚！

sum[4] = d[1] ? 4 + d[2] ? 3 + d[3] ? 2 + d[4] ? 1;

刚才豁然开朗的赶脚，是不是很开心？

那我们再开心开心！

sum[4] = d[1] ? 4 + d[2] ? 3 + d[3] ? 2 + d[4] ? 1;

= (d[1] ? 5 + d[2] ? 5 + .. d[4] ? 5) - d[1] ? 1 + d[2] ? 2 + .. d[4] ? 4;

所以如果我们要求sum[i];

sum[i] = (i + 1)?(d[1] + d[2] + .. d[i]) - (d[1]?1 + d[2] ? 2 + .. d[i] ? i);

现在我们尝试将这个式子与前缀和联系起来:

看这个 (d[1] + d[2] + .. d[i])

这不是 d[i]的前缀和吗？！

再看这个 (d[1]?1 + d[2] ? 2 + .. d[i] ? i)

如果我们考虑再弄一个数组d2。

d2[i] = d[i] * i;

带入一下 (d2[1] + d2[2] + .. d2[i])

就变成了d2的前缀和！

所以我们将a数组差分后放进d数组里，初始化d2[i] = d[i] * i

我们就可以弄两个树状数组，一个维护d，一个维护d2

接下来放 P3372的代码。大家也可以去做一下（用树状数组哦）

首先需要这俩

LL d_tr[100005],d2_tr[100005]; // 分别是维护d和d2的树状数组 

这是更新操作

void add(int x,LL v) // 在x的位置加上v
{
    for(int i = x;i <= n;i += lowbit(i)){
        d_tr[i] += v;
        d2_tr[i] += x * v;
    } 
    // 因为 d2_tr[x] += d_tr[x] * x;
    // d_tr[x] += v;所以我们要更新d2_tr[x] = (d_tr[x] + v) * x;
    // 就相当于 d2_tr[x] += x * v;
    // 然后向上更新 
    // 循环中的i是用来代替向上更新的x的,不懂得可以手动模拟一下~ 
}

这是查询

LL sum(int x) // 查询前缀和
{
    long long ans = 0;
    for(int i = x;i > 0;i -= lowbit(i)){
        ans += (x+1) * d_tr[i] - d2_tr[i];
    }
    // 根据我们推出来的东西求前缀和
    // 不懂的话，手动模拟依旧是个好办法 
    return ans;
}

输入时的初始化

for(int i = 1;i <= n;i++){
        scanf("%lld",&a[i]);
        add(i,a[i] - a[i-1]); // 将差分后的值放入树状数组 
    }

主函数中的更新记得写成这样

    add(x,v);       //区间更新操作，差分的知识 
    add(y+1,-v);

主函数中的查询记得写成这样

    LL ans = sum(y) - sum(x-1); //前缀和之差算区间和 
    printf("%lld\n",ans);

简单理解一维树状数组区间求和+修改

原文：https://www.cnblogs.com/Blue-nine9/p/9414232.html