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

单点更新，区间查询

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

代码如下：

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);
}