进阶版树状数组

glm233

发布于 2020-09-28 02:30:25

45300

代码可运行

文章被收录于专栏：glm的全栈学习之路glm的全栈学习之路

运行总次数：0

代码可运行

我们都知道树状数组一般有两种形式

1.最为传统的版本，支持区间求和，单点修改

2.差分树状数组支持区间修改，单点查询

而进阶版树状数组可支持区间求和，区间修改

其原理是：

设tree[i]=a[i]-a[i-1]（差分），那么容易得到：

tree[1]+tree[2]+……+tree[i]=a[i]这个公式

维护tree数组即可以实现区间修改了。

接下来是区间查询的实现问题

我们已经推出了一个公式：

tree[1]+tree[2]+……tree[i]=a[i]

那么，对于1到r的区间和，即为：

 a[1]+a[2]+……+a[r-1]+a[r]
//用上方公式推导得出
=tree[1]+(tree[1]+tree[2])+……+(tree[1]+……+tree[r])
//根据加法交换律与结合律：
=(tree[1]*(r))+(tree[2]*(r-1))+……(tree[r]*1)
//那么：
=r*(tree[1]+tree[2]+……+tree[r])-(tree[1]*0+tree[2]*1+……+tree[r]*(r-1))

看到这里，是不是已经很清晰了呢？

对于a的树状数组(差分)tree，建立一个新的树状数组tree1使得：

tree1[i]=tree[i]*(i-1)

之后，x到y的区间和即为：

(y*query(tree,y)-(x-1)*query(tree,x-1))-(query(tree1,y)-query(tree1,x-1))

P3372 【模板】线段树 1

这种树状数组可以实现线段树的某些功能

#include<bits/stdc++.h>
#define rg register
#define inf 2147483647
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
#define maxn 100005
const double eps=1e-8;
using namespace std;
inline ll read()
{
    char ch=getchar();ll s=0,w=1;
    while(ch<48||ch>57){if(ch=='-')w=-1;ch=getchar();}
    while(ch>=48&&ch<=57){s=(s<<1)+(s<<3)+ch-48;ch=getchar();}
    return s*w;
}
inline void write(ll x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+48);
}
ll n,m;
ll tree[maxn],tree1[maxn];
inline ll lb(ll x)
{
    return x&-x;
}
inline void add(ll *tree,ll x,ll k)
{
    for(;x<=n;x+=lb(x))
    {
        tree[x]+=k;
    }
}
inline ll query(ll *tree,ll x)
{
    ll ans=0;
    for(;x;x-=lb(x))
    {
        ans+=tree[x];
    }
    return ans;
}
int main()
{
    n=read(),m=read();
    ll now,last=0;
    for( rg ll i=1;i<=n;i++)
    {
        now=read();
        add(tree,i,now-last);
        add(tree1,i,(now-last)*(i-1));
        last=now;
    }
    for(rg ll i=1;i<=m;i++)
    {
        ll x;
        x=read();
        if(x==1)
        {
            ll a,b,c;
            a=read(),b=read();c=read();
            add(tree,a,c);
            add(tree,b+1,-c);
            add(tree1,a,c*(a-1));
            add(tree1,b+1,-c*b);
        }
        else if(x==2)
        {
           ll  a,b;
           a=read(),b=read();
           cout<<b*query(tree,b)-(a-1)*query(tree,a-1)-(query(tree1,b)-query(tree1,a-1))<<endl;
        }
    }
    return 0;
}