树状数组维护区间和和区间修改

作用

可以用树状数组在(n*logn)内,虽然线段树也能,但是树状数组的代码,空间都要比它优越得多.

实现方法

首先我们可以用差分的方法使区间修改可以在log的复杂度完成,但重点在于区间和的查询.

我们知道,此时num[i]=a[1]+a[2]+……a[i],可以利用树状数组快速求出.

而区间和则是(a[1]+a[2]+……a[i])+(a[1]+a[2]+……a[i-1])……..+(a[1]+a[2])+a[1].

也就是i*(a[1]+a[2]+……a[i])-(a[1] * 0+a[2] * 1……a[i] *(i-1)).

前半部分可以用树状数组维护,后面可以再建一个树状数组维护(i-1)*a[i]的前缀和.

就可以用两个树状数组维护区间和和区间修改

代码

以洛谷 P3372 【模板】线段树 1为例.

#include<iostream>
#include<cstdio>
#define lb(x) (x&(-x))
#define ll long long
#define N 100100
using namespace std;

ll n,m,s1[N],s2[N],num[N];

inline void add(ll u,ll v,ll w)
{
    for(;u<=n;u+=lb(u))
    {
        s1[u]+=v;
        s2[u]+=w;
    }
}

inline ll ask(ll u)
{
    ll res=,i;
    for(i=u;i;i-=lb(i))
    {
        res+=s1[i];
    }
    res*=u;
    for(i=u;i;i-=lb(i))
    {
        res-=s2[i];
    }
    return res;
}

int main()
{
    ll i,j,o,p=,q;
    cin>>n>>m;
    for(i=;i<=n;i++)
    {
        scanf("%lld",&num[i]);
        q=num[i];
        num[i]-=p;
        p=q;
    }
    for(i=;i<=n;i++)
    {
        add(i,num[i],num[i]*(i-));
    }
    for(i=;i<=m;i++)
    {
        scanf("%lld",&o);
        if(o==)
        {
            scanf("%lld%lld%lld",&p,&q,&o);
            add(p,o,(p-)*o);
            add(q+,-o,-q*o);
        }
        else
        {
            scanf("%lld%lld",&p,&q);
            printf("%lld\n",ask(q)-ask(p-));
        }
    }
}