C81【模板】树状数组 点修+区查 区修+点查

/*
【方法1（超时）】： 
数据结构：
1、int a[]数组：a[i]表示第i个数的值
2、int s[]数组：s[i]表示前i个数的和，即s[i]=a[1]+a[2]+a[3]+…+a[i]
算法分析：
1、求和（快）：a[x]+a[x+1]+a[x+2]+…+a[y] = s[y] - s[x-1] 。
2、修改（慢）：直接修改a[x]=k，但为了维护s数组，a[x]改变了，那么s[x] 、s[x+1]、s[x+2]…s[n]都要改变。

【方法2（树状数组）】： 
数据结构：
1、int a[]数组：a[i]表示第i个数的值
2、int c[]数组：c数组作用类似方法1中的s数组，
c[i]表示以第i个数为结束的连续后缀和，即s[i]= a[?]+…+a[i-2]+a[i-1]+a[i] （“?“以后解释）
算法分析：
1、a[x]改变了，c数组中需要改变的个数不多（log n个，log(1百万)约等于20）。
2、通过x在log n步（很快）获得a[1]+a[2]+a[3]+…+a[x]的值。

算法过程：
1、核心代码（三个函数）：
（1）、lowbit(x)函数：得到x的二进制形式下最低位1的权值，比如：20=(10100)2，lowbit(20) =4=(100)2
int lowbit(int x) { return x&-x;}//代码可硬背，幸好容易背：自己和自己的负数与运算。
解释：设8位整数（最高位为符号位）x是：(01010100)2，显然lowbit(x)=4。
-x的原码是：11010100，-x的反码是：10101011，-x的补码是：10101100，所以x & -x=100。

（2）、add(x,k)函数：执行a[x]+k，并且维护c数组相关位置修改，何谓“相关位置“后面讲。
void add(int x,int k)
{
	a[x]=a[x]+k;//这句话没用，这里只是为了让代码和讲解一致
	while(x<=n) c[x]+=k, x+=lowbit(x);
}

（3）、getsum(x)函数：获得a[1]+a[2]+a[3]+…+a[x]的值
int getsum(int x)
{
	int s=0;
	while(x>=1) s+=c[x], x-=lowbit(x); 
	return s;
}
2、重点过程：
（1）、getsum函数：
c数组（树状数组）和a数组的关系如下：
??c[1] =a[1]  ----------------------------C[(1)2] 管1个
??c[2] =a[1]+a[2] ------------------------C[(10)2] 管2个
??c[3] =a[3] -----------------------------C[(11)2] 管1个
??c[4] =a[1]+a[2]+a[3]+a[4] --------------C[(100)2] 管4个
??c[5] =a[5] -----------------------------C[(101)2] 管1个
??c[6] =a[5]+a[6] ------------------------C[(110)2] 管2个
??c[7] =a[7] -----------------------------C[(111)2] 管1个 
??c[8] =a[1]+a[2]+a[3]+…+a[8] -----------C[(1000)2] 管8个
??......?
C[16]=a[1]+a[2]+a[3]+…+a[16] ------C[(10000)2] 管16个
......?
研究c[x]，x转为二进制，后面有连续k个0，那么c[x]管2^k个，具体如下：
c[x]=a[x–2^k+1]+…+a[x-2]+a[x-1]+a[x]，2^k=lowbit(x)。
例子：模拟求a[1]+a[2]+a[3]+…+a[91]的过程。
c[91]管1个：a[91]，因为lowbit(91)=lowbit( (1011011)2 )= (1)2 =1
91–lowbit(91)=91-1=90
c[90]管2个：a[89] +a[90]，因为lowbit(90)=lowbit( (1011010)2 )= (10)2 =2
90–lowbit(90)=90-2=88
c[88]管8个：a[81]+a[82]+…+a[88] ，因为lowbit(88)=lowbit( (1011000)2 )= (1000)2 =8
88–lowbit(88)=88-8=80
c[80]管16个：a[65]+a[66]+…+a[80] ，因为lowbit(80)=lowbit( (1010000)2 )= (10000)2 =16
80–lowbit(80)=80-16=64
c[64]管64个：a[1]+a[2]+…+a[64] ，因为lowbit(64)=lowbit( (1000000)2 )= (1000000)2 =64
可得：
a[1]+a[2]+a[3]+…+a[90]+a[91]=c[64]+c[80]+c[88]+c[90]+c[91]
（2）、add函数：
	举个例子：c[88]管8个：a[81]+a[82]+…+a[88] ，因为lowbit(88)=lowbit( (1011000)2 )= (1000)2 =8，
        也就是a[81]、a[82]、a[83]、…a[88]这8个数的任何一个改变了都要及时通知c[88]，这8个数有以下性质：
	设x=81至88其中一个数，（包括88自己）不断执行x=x+lowbit(x)，x总会等于88。
	而设x=1至80其中一个数，不断执行x=x+lowbit(x)，x一定不会等于88。
*/
#include<bits/stdc++.h> 
using namespace std;
typedef long long LL;
const LL N=1e6+10;
LL n,a[N],c[N];
void add(LL x,LL k)
{
    for(;x<=n;x+=x&-x)c[x]+=k;
}
LL getsum(LL x)
{
    LL res=0;
    for(;x>=1;x-=x&-x)res+=c[x];
    return res;
}
int main()
{
    LL m;scanf("%lld%lld",&n,&m);
    memset(c,0,sizeof(c));
	for(LL i=1;i<=n;i++)scanf("%lld",&a[i]),add(i,a[i]);
    for(LL i=1,op,x,y;i<=m;i++)
    {
        scanf("%lld%lld%lld",&op,&x,&y);
        if(op==1)add(x,y);
        else
        {
            if(x>y)swap(x,y);
            printf("%lld\n",getsum(y)-getsum(x-1));
        }
    }
    return 0;
}