树状数组(单点修改区间查询、区间修改单点查询、区间修改区间查询)

版权声明：本文为CSDN博主「Zars19」的原创文章，遵循CC 4.0 by-sa版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/zars19/article/details/54620021

Description

分别对应的三道模板裸题： 
[luogu P3374]树状数组 1
[luogu P3368]树状数组 2
[CodeVS 1082]线段树练习 3

Solution

一个很优美的数据结构 
放图一张帮助日后忘记的时候回忆（图自百度百科） 

单点修改 区间查询

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n,m;
int c[500005];
int lowbit(int x)
{
    return (-x)&x;
}
void add(int pos,int x)
{
    while(pos<=n)
    {
        c[pos]+=x;
        pos+=lowbit(pos);
    }
}
void input()
{
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        add(i,x);
    }
}
int query(int pos)
{
    int res=0;
    while(pos>0)
    {
        res+=c[pos];
        pos-=lowbit(pos);
    }
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    input();
    int f,x,y;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&f,&x,&y);
        if(f==1)
        add(x,y);
        else if(f==2)
        cout<<query(y)-query(x-1)<<endl;
    }
    return 0;
}

区间修改 单点查询

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
int c[500005];
int n,m;
int lowbit(int x)
{
    return x&(-x);
}
void add(int pos,int x)
{
    while(pos<=n)
    {
        c[pos]+=x;
        pos+=lowbit(pos);
    }
}
int query(int pos)
{
    int res=0;
    while(pos>0)
    {
        res+=c[pos];
        pos-=lowbit(pos);
    }
    return res;
 } 
int main()
{
    scanf("%d%d",&n,&m);
    int x=0,y;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&y);
        add(i,y-x);
        x=y;
    }
    int opt,k;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d%d",&x,&y,&k);
            add(x,k);
            add(y+1,-k);
        }
        else if(opt==2)
        {
            scanf("%d",&x);
            printf("%d\n",query(x));
        }
    }
    return 0;
 } 

区间修改 区间查询*

此处简略地说明一下 
原数组a，差分数组d 则有 
an=∑i=1ndian=∑i=1ndi 
所以 
∑i=1nai=∑i=1n∑j=1idj=∑i=1n(n−i+1)×di∑i=1nai=∑i=1n∑j=1idj=∑i=1n(n−i+1)×di 
=(n+1)×∑i=1ndi−∑i=1ndi×i=(n+1)×∑i=1ndi−∑i=1ndi×i 
于是我们维护两个树状数组，c1储存didi，c2储存di×i
 

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
long long c[200005][2];
int n,q;
int lowbit(int x)
{
    return x&(-x);
}
void add(int pos,int x,int f)
{
    while(pos<=n)
    {
        c[pos][f]+=x;
        pos+=lowbit(pos);
    }
}
long long query(int pos,int f)
{
    long long res=0;
    while(pos>0)
    {
        res+=c[pos][f];
        pos-=lowbit(pos);
    }
    return res;
 }
long long ask(int pos)
{
    long long res=(pos+1)*query(pos,0)-query(pos,1);
    return res; 
}
int main()
{
    scanf("%d",&n);
    int a=0,b,opt,x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&b);
        add(i,b-a,0);
        add(i,(b-a)*i,1);
        a=b;
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d%d",&a,&b,&x);
            add(a,x,0);
            add(b+1,-x,0);
            add(a,x*a,1);
            add(b+1,-x*(b+1),1);
        }
        else if(opt==2)
        {
            scanf("%d%d",&a,&b);
            printf("%lld\n",ask(b)-ask(a-1));
        }
    }
    return 0;
}