二进制操作和树状数组

# 二进制运算符 - `a&b` 按位与（二进制中的每一位都执行与运算，如`01010101`和`10111011`，结果为00010001） - `a|b` 按位或（二进制中的每一位都执行或运算） - `a>>n` 右移运算（二进制的每一位都向右移动n位，相当于`a/(2^n)`） - `a<<n` 左移运算（二进制的每一位都向左移动n位，相当于`a*(2^n)`）（谨防数位溢出） # 二进制运算技巧 - `a&1` 把a和1按位与，则a为单数时值为1，为双数时值为0。 - `a&-a` 把a和-a按位与，可求出a的最低位1，也就是lowbit。 以下给出原理： _我们知道一个数加一个负号是把这个数的二进制取反+1,_ _负数用在计算机中用补码表示_ _负数的反码 是其正数的原码 取反_ _负数的补码 是 其正数的原码取反 + 1_ _[10]原码 = 1010_ _[-10]反码 = 0101_ _[-10]补码 = 0110_ _如-10的二进制就是-1010=0101+1=0110，_ _然后用1010&0110，_ _答案就是0010了！_ # 树状数组 先上代码。 ```cpp #include <bits/stdc++.h> using namespace std; int n,m,t,x,y,j,sum; int a[500005],tree[500005]; int lowbit(int i) {//lowbit：获得最低的一个1 return i&-i;//i&-i，记住就行 } int main() { scanf("%d %d",&n,&m); for(int i=1; i<=n; i++) { scanf("%d",&a[i]); j=i; while(j<=n) { tree[j]+=a[i];//每个节点都添加当前的值，预处理 j+=lowbit(j);//进入下一个“更高节点级”的节点 } } for(int i=0; i<m; i++) { scanf("%d %d %d",&t,&x,&y); if(t==1) { j=x; while(j<=n) { tree[j]+=y; j+=lowbit(j); }//加法操作，和初始化操作同理 } else { sum=0; while(y) { sum+=tree[y]; y-=lowbit(y); }//获取1-y x-=1; while(x) { sum-=tree[x]; x-=lowbit(x); }//获取1-x，并执行(1+...+y)-(1+...+x) cout<<sum<<endl; } } return 0; } ``` 原理如下： _（图片来自于网上，来源已不可考）_