树状数组进阶篇：区间修改，区间查询

单点更新，区间查询

我们知道，树状数组最基本的功能是单点更新，区间查询

代码如下：

int lowbit(int x)
{
    return x & (-x);
}
void add(int x, int val)
{
    while (x <= n)
    {
        tree[x] += val;
        x += lowbit(x);
    }
}
int ask(int x)
{
    int res = 0;
    while (x)
    {
        res += tree[x];
        x -= lowbit(x);
    }
    return res;
}

区间更新，单点查询

通过 “单点更新，区间查询” 功能+差分的思想，我们实现了：区间更新，单点查询

$c[i]=a[i]-a[i-1]$ ,所以,以c[i] 建立树状数组， $a[i]=ask(i)$

因为 $a[i]=\sum_{j=1}^i c[i]$

所以我们想让区间 $[l,r]$ 每一个a[i] 都加上x的话，我们只需要 $add(l,x),add(r+1,-x)$

进入我们今天的主题：区间更新，区间查询

我们知道数组a[i]的差分数组 c[i] 满足： $a[i]=\sum_{j=1}^i c[i]$

那么 $\sum_{i=1}^na[i]=\sum_{i=1}^n{\sum_{j=1}^ic[i]}$

$\sum_{i=1}^na[i]=c[1]+(c[1]+c[2])+(c[1]+c[2]+c[3])+\dots+\sum_{j=1}^n c[i]$

$\sum_{i=1}^na[i]=n*(c[1]+c[2]+c[3]+\dots+c[n])-(c[2]+2*c[3]+3*c[4]+\dots+(n-1)*c[n])$

$\sum_{i=1}^na[i]=n*(\sum_{i=1}^n c[i])- \sum_{i=1}^n(i-1)*c[i]$

于是我们可以用2个树状数组，分别维护 $c[i]$ 和 $(i-1)*c[i]$ ，数组名分别叫tree1,tree2

区间 $[l,r]$ 的sum和就等于 $query(r)-query(l-1)$

$query(x)=x*ask(tree1,x)-ask(tree2,x)$

如果怕询问 $[0,x]$ 等情况 $(i-1)<0$ ，可以第二个树状数组tree2维护 $(i*c[i])$ ,根据差分数组的思想，并不影响结果。

代码：

long long tree1[maxn];
long long tree2[maxn];

long long ask(long long *tree, long long x) {
    long long sum = 0;
    for (; x; x -= (x & -x)) {
        sum += tree[x];
        sum %= mod;
    }
    return sum;
}

void add(long long *tree, long long x, long long y) {
    for (; x <= n; x += (x & -x))
    {
        tree[x] += y;
        tree[x] %= mod;
    }
}

ll query(ll l, ll r)
{
    long long  ans = 0;
    ans = ( (r + 1) * ask(tree1, r) - ask(tree2, r) ) -(  l * ask(tree1, l - 1)  - ask(tree2, l - 1) );
    return ans;
}
void op(ll l, ll r , ll x)
{
    add(tree1, l, x);
    add(tree1, r + 1, -x);
    add(tree2, l, l * x);
    add(tree2, r + 1, -(r + 1) * x);
}

树状数组 进阶篇：区间修改，区间查询