树状数组相信大家都很熟悉了，而今天我将会为大家带了一些更加全面的操作，并且欢迎补充哦。
其实我想说的是，除了RMQ，线段树能做的，树状数组都能做。换句话说，这是一个稍微进阶版的的树状数组，读者至少要会单调修改区间查询这个最基本的操作。
树状数组应该算是常数非常小的数据结构啦。而小生特别喜欢这个数据结构，这是因为它特别短，就是又短又快！
这是树状数组的核心操作，看到了这个操作基本上就是树状数组了。
现在我们来看看这个操作的实际意义：
抛结论：令p=lowbit(x),则p在x在二进制下从右往左第一个1的位置上也为1，其它为0。
举个例子:lowbit( ( 110 )2 ) = (10)2
我觉得这个。。。很简单吧
这里就是利用差分的思想。
令a为原数组
令一个新的数组b:b[1]=a[1],b[i]=b[i]-b[i-1]。(差分数组)
那么a[i]=b[1]+b[2]+….+b[i]
这样我们用树状数组维护差分数组b即可，也就不维护原数组了，每次修改区间的时候只会有两个b被修改，因此可以在log级别完成查找与维护。
此外，由于任何一段b的区间和都可以写成两个a的差，因此一般情况下b的储存类型和a是相同的。
基于区间修改单点查询
我们看看前缀和怎么求，区间的话直接用前缀和减就可以了。
任然令a为原数组，b为差分数组
现在求a的前M项前缀和
a[1]+a[2]+a[3]+....+a[m] =(b[1])+(b[1]+b[2])+(b[1]+b[2]+b[3])+...+(b[1]+b[2]+b[3]+...+b[m]) =m*b[1]+(m-1)*b[2]+...+1*b[m] =m*(b[1]+b[2]+b[3]+...+b[m])-（0*b[1]+1*b[2]+2*b[3]+...+(m-1)*b[m]）显然的，我们再求一个数组c，表示(i-1)*b[i]
这样我们维护b数组和c数组的前缀和就可以实现a数组的区间修改和区间查询了。
表达式：suma(m)=m*sumb(m)-sumc(m)
这里维护b数组的前缀数组依旧可以和a的类型相同，但是维护c数组的数组多半需要开LL（极限不会超过n*a的）。
基于权值树状数组，要用到前面强调的lowbit操作。
根据一种很神奇的倍增思想。。。
就是根据倍增思想， 当我们把一个数加上2^k后（之前加的k都比当前k大），我们的c数组（树状数组），c[i+ 2^k]的值就是我们增加的这一段权值的个数（记住我们是权值树状数组哦）。就可以直接判断当前元素个数是否超过了K，超过了就退回去，否则就保留。
这种问题还去用线段树真是麻烦哎。
这么弱智就不贴了吧
这么弱智也不贴了吧
这么弱智。。。。 我贴。。。
struct BIT { int c1[maxn]; LL c2[maxn]; void Initial() { memset(c1,0,sizeof(c1)); memset(c2,0,sizeof(c2)); } int lowbit(int x) { return x&(-x); } void update(int i,int j,int x) { LL ad1=1ll*(i-1)*x,ad2=1ll*j*x; for(int t=i;t<=n;t+=lowbit(t))c1[t]+=x,c2[t]+=ad1; for(int t=j+1;t<=n;t+=lowbit(t))c1[t]-=x,c2[t]-=ad2; } LL sum(int i) { LL ret=0; for(int t=i;t;t-=lowbit(t))ret+=1ll*i*c1[t],ret-=c2[t]; return ret; } }bit;果然短小精干吧，比线段树好多了吧。。（ZKW线段树除外，这两者本身就有密不可分的联系）
核心代码：
//这里是第K小元素 //oo=floor(log2(n)) int Kth(int k) { int ans=0,cnt=0; for(int i=oo;i>=0;i--) { ans+=(1<<i); if(ans>N || cnt+c[ans]>=k)ans-=(1<<i); else cnt+=c[ans]; } return ++ans; }代码注意： - 这里cnt+c[ans]>=k返回是为了防止跳过，最后会停在正确答案的前一个位置，重复元素也不会影响结果。 - 最后还可以通过ans返回n+1来判断是否存在第K大元素
