树状数组

洛谷P3374 【模板】树状数组 1

已知一个数列，你需要进行下面两种操作：

1.将某一个数加上x

2.求出某区间每一个数的和

先来定义一个东西：lowbit

记lowbit(x)为x的二进制最低位包含后面的0构成的数.

举几个栗子:

8的二进制表示是1000，lowbit(8) =1000₍₂₎= 8

6的二进制是110，lowbit(6) =10₍₂₎= 2

求lowbit

记f[i]是i的最低位.

若i是奇数,f[i] = 1,否则f[i] = f[i/2] * 2.

是不是有点麻烦QwQ

其实可以这样：

int lowbit(int x)
{
        return x&-x;  
}

由于电脑一种叫做补码的操作（由于电脑是二进制，它们存的相反数是它的取反+1），一个数与它的相反数做与操作时会返回二进制下最右边的1的位置。举个例子： 6&-6=2 将6变成二进制：110。其中最右侧的1加粗字体：110则返回的是二进制下10的值：

再来介绍一下树状数组

树状数组是一种用来求前缀和的数据结构.

对于原始数组A，我们设一个数组C

C[i]=A[i-lowbit(i)+1]+...+A[i]

i>0的时候C[i]才有用，C就是树状数组

大概就是这样：

第一位（1在二进制下=1 二进制下的1=1）的值为输入的数组的第一位往前的一位的和，也就是第一位。
第二位（2在二进制下=10 二进制下的10=2）的值为输入的数组的第二位往前两位的和，第一位和第二位。
第三位（3在二进制下=11 二进制下的1=1）的值为输入的数组的第三位往前一位的和，也就是第三位。
第四位的值（4在二进制下=100 二进制下的100=4）的值为输入的数组的第四位往前四位的和，也就是第一位，第二位，第三位以及第四位

树状数组用于解决单个元素经常修改，而且还反复求不同区间和的情况

树状数组求和

树状数组只能够支持询问前缀和，不支持区间和，但是可以用前缀和求区间和.

我们先找到C[n],然后我们发现现在，下一个要找的点是n − lowbit(n)，然后我们不断的减去lowbit(n)并累加C数组.

我们可以用前缀和相减的方式来求区间和.

询问的次数和n的二进制里1的个数相同，时间复杂度是O(log N).

代码：

int ask(int x) //查询[1,x]的值 
{
        int ans=0;
        for (;x;x-=lowbit(x)) ans+=s[x];
 //我们询问的]是[x-lowbit(x)+1,x,然后后面一个区间是以x-lowbit(x)为右端点的，依次类推 
        return ans;
}

树状数组更新

现在我们要修改Ax的权值,考虑所有包含x这个位置的区间个数.

从C[x]开始,下一个应该是C[y = x + lowbit(x)],再下一个是C[z = y + lowbit(y)]...直到达到上限

注意到每一次更新之后,位置的最低位1都会往前提1.总复杂度也为O(log N).

大概就是这样：

代码：

void ins(int x,int y)//修改a[x]的值,a[x]+=y;
{
        for (;x<=n;x+=lowbit(x)) s[x]+=y;
 //首先需要修改的区间是以x为右端点的,然后下一个区间是x+lowbit(x),以此类推 
}

所以这一个题的代码就出来了：

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<time.h>
#include<queue>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-1);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
ld eps=1e-9;
ll pp=1000000007;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll read(){
    ll ans=0;
    char last=' ',ch=getchar();
    while(ch<'0' || ch>'9')last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans;
    return ans;
}
//head

using namespace std;

int m,n,s[5000005];

long long ans;

int lowbit(int x)
{
        return x&-x;  
}

void ins(int x,int y)//修改a[x]的值,a[x]+=y;
{
        for (;x<=n;x+=lowbit(x)) s[x]+=y; //首先需要修改的区间是以x为右端点的,然后下一个区间是x+lowbit(x),以此类推 
}

int ask(int x) //查询[1,x]的值 
{
        int ans=0;
        for (;x;x-=lowbit(x)) ans+=s[x]; //我们询问的]是[x-lowbit(x)+1,x,然后后面一个区间是以x-lowbit(x)为右端点的，依次类推 
        return ans;
}

int main()
{
    n=read(),m=read();
    rep(i,1,n)
    {
        int t=read();
        ins(i,t);
    }
        
    rep(i,1,m)
    {
        int a,b,c;
        a=read(),b=read(),c=read();
        if(a==1)
        {
            ins(b,c);
        }
        if(a==2)
        {
            printf("%d
",ask(c)-ask(b-1));//区间查询则为右边界前缀和减去左边界前缀和 
        }
    }
}

洛谷P3368 【模板】树状数组 2

已知一个数列，你需要进行下面两种操作：

1.将某区间每一个数加上x

2.求出某一个数的值

树状数组区间修改

如果将x到y区间加上一个k，那就是从x到n都加上一个k，再从y+1到n加上一个-k

加的移动还是i+=lowbit(i);

或者说叫差分

差分：

设数组a[]={1,6,8,5,10}，那么差分数组b[]={1,5,2,-3,5}

也就是说b[i]=a[i]-a[i-1];(a[0]=0;)，那么a[i]=b[1]+....+b[i];(这个很好证的)。

假如区间[2,4]都加上2的话

a数组变为a[]={1,8,10,7,10}，b数组变为b={1,7,2,-3,3};

发现了没有，b数组只有b[2]和b[5]变了，因为区间[2,4]是同时加上2的,所以在区间内b[i]-b[i-1]是不变的.

所以对区间[x,y]进行修改,只用修改b[x]与b[y+1]:

b[x]=b[x]+k;b[y+1]=b[y+1]-k;

就像这样

ins(b,d);
ins(c+1,-d);

树状数组单点查询

查询和求和是一样的（代码其实也一样）。注意我们的操作不是区间求和，而是求两个前缀和的差！

int ask(int x) 
{
        int ans=0;
        for (;x;x-=lowbit(x)) ans+=s[x];
        return ans;
}

所以最后的代码是这样的：

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<time.h>
#include<queue>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pr;
const double pi=acos(-1);
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,n,a) for(int i=n;i>=a;i--)
#define Rep(i,u) for(int i=head[u];i;i=Next[i])
#define clr(a) memset(a,0,sizeof a)
#define pb push_back
#define mp make_pair
#define fi first
#define sc second
ld eps=1e-9;
ll pp=1000000007;
ll mo(ll a,ll pp){if(a>=0 && a<pp)return a;a%=pp;if(a<0)a+=pp;return a;}
ll powmod(ll a,ll b,ll pp){ll ans=1;for(;b;b>>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}
ll read(){
    ll ans=0;
    char last=' ',ch=getchar();
    while(ch<'0' || ch>'9')last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans;
    return ans;
}
//head

using namespace std;

int m,n,t[5000005],s[5000005];

long long ans;

int lowbit(int x)
{
        return x&-x;  
}

void ins(int x,int y)
{
        for (;x<=n;x+=lowbit(x)) s[x]+=y; 
}

int ask(int x) 
{
        int ans=0;
        for (;x;x-=lowbit(x)) ans+=s[x];
        return ans;
}

int main()
{
    n=read(),m=read();
    rep(i,1,n)
    {
        t[i]=read();
    }
        
    rep(i,1,m)
    {
        int a;
        a=read();
        if(a==1)
        {
            int b=read(),c=read(),d=read();
            ins(b,d);
            ins(c+1,-d);
        }
        if(a==2)
        {
            int b=read();
            printf("%d
",t[b]+ask(b));
        }
    }
}

PS.这里s数组存的是原数组t每一个元素增加或减少的多少