树状数组——一个简单的整数问题2

树状数组——一个简单的整数问题_北岭山脚鼠鼠的博客-CSDN博客的升级版 

传送门：243. 一个简单的整数问题2 - AcWing题库

思路：原本简化版的是区间增加和单点查询，先在变成了去区间增加+区间查询，难度瞬间上升

在原本的问题里面，b数组的前缀和就是增加过后a[x]增加的值。

到这里后对于某一个区间[1,x]增加的值就是

又可以改写成

具体推导过程如下图：

 结合上述的全部需要做的操作就是，建两个树状数组c0和c1,一个用来存上图中红加黑的部分，一个用来存红色的部分。

对于每条增加指令有如下2步

1.在c0中 ，c0[l]+=d ,  c0[r+1]- = d;

2.在c1中，c1[l]+=l*d, c1[r+1]- =(r+1)*d;

 靠c1和c0就可以做到，这里求的是区间内整体增加的数值。

对原序列a改造成前缀和数组a即可。

代码：
 

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll c[2][N];
ll a[N];
ll sum[N];
int n,m;
int lowbit(int x)//作用：得到x的二进制下最小的2的次幂
{
    return x&(-x);
}
void add(int k ,int x,int y)
{
    for(;x<=n;x+=lowbit(x)) c[k][x]+=y;
}
ll ask(int k,int x)
{
    ll ans=0;
    for(;x;x-=lowbit(x)) ans+=c[k][x];
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        a[i]+=a[i-1];
    }
    while(m--)
    {
        char op[2];
        int l,r;
        scanf("%s%d%d",op,&l,&r);
        if(op[0]=='Q')
        {
            ll ans=a[r]-a[l-1];
            ans+=(r+1)*ask(0,r)-l*ask(0,l-1);
            ans-=ask(1,r)-ask(1,l-1);
            printf("%lld\n",ans);
        }else
        {
           int x;
            scanf("%d",&x);
            add(0,l,x);
            add(0,r+1,-x);
            add(1,l,l*x);
            add(1,r+1,-(r+1)*x);
        }
    }
    return 0;
}

线段树做法：

思路：众所周知，线段树可以支持O(logn)的时间复杂度的区间查询，但如果要进行区间修改的话会导致所有区间的在该区间内的节点的子树下的子节点的信息都要被修改，时间复杂度度为O(N).

如果之后却根本没有用到修改后的区间的信息则前面的修改操作都是浪费时间的，所以这里我们要给当前节点的区间都在修改区间内的节点都加上一个懒标记，并完成当前节点的修改，而至于该节点下的子树的修改则是留到下一次查询或者区间修改的时候将懒标记下传。

代码：
 

#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e5+10;
struct tree
{
    int l, r;
    ll sum,add;
}t[N<<2];
ll a[N];
int n,m;
void pushdown(int p)
{
    if(t[p].add)
    {
        t[p*2].sum+=t[p].add*(t[p*2].r-t[p*2].l+1);
         t[p*2+1].sum+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
         t[p*2].add+=t[p].add;
         t[p*2+1].add+=t[p].add;
         t[p].add=0;
    }
}
void build(int p,int l,int r)
{
    t[p].l=l;
    t[p].r=r;
    if(l==r) {t[p].sum=a[l];return ;}
    int mid=(l+r)/2;
    build(2*p,l,mid);
    build(2*p+1,mid+1,r);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
void change (int p,int l,int r,int d)
{
    if(l<=t[p].l&&t[p].r<=r)
    {
        t[p].sum+=(ll) d*(t[p].r-t[p].l+1);
        t[p].add+=d;
        return;
    }
    pushdown(p);
    int mid=(t[p].l+t[p].r)/2;
    if(l<=mid) change(2*p,l,r,d);
    if(r>mid) change(2*p+1,l,r,d);
    t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
ll ask(int p,int l,int r)
{
    if(l<=t[p].l&&t[p].r<=r) return t[p].sum;
    pushdown(p);
    int mid=(t[p].r+t[p].l)>>1;
    ll sum=0;
    if(l<=mid) sum+=ask(2*p,l,r);
    if(r>mid) sum+=ask(2*p+1,l,r);
    return sum;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,1,n);
    while(m--)
    {
        char op[2];
        int l,r,d;
        scanf("%s",op);
        if(op[0]=='Q')
        {
            scanf("%d%d",&l,&r);
            printf("%lld\n",ask(1,l,r));
        }else
        {
            scanf("%d%d%d",&l,&r,&d);
            change(1,l,r,d);
        }
    }
    return 0;
}