树状数组颂

树状数组,圣洁美丽,
二进制光芒照大地.
我们心中充满热情
来到你的圣殿里,
你的魔力能使人们
消除一切TLE.
在你光辉照耀下面,
人们AC成兄弟.

int tree[100000];
void iniTree(){memset(tree,0,sizeof(tree));}
inline int Lowbit(int a){return a&-a;}
void ins(int a,int b){//若b==1，插入元素a。若b==-1，删除元素a
     while (a<N){
           tree[a]+=b;
           a+=Lowbit(a+1);
     }
}
int findKth(int k){//寻找第k大的元素
    int i,j;
    i=0;
    while (1){
          j=0;
          while (i<N && tree[i]<k)i+=(j=Lowbit(i+1));
          i-=j;
          k-=tree[i];
          if (!k)break;
          ++i;
          if (Lowbit(i+1)!=1)break;
    }
    return i;
}
推荐：
http://www.wiskey86.cn/wordpress/?p=26
不过是用线段树写的。

• 打油诗啊........,偶一直不会树壮数组,郁闷 (0) smallbox 2009-05-15 13:06:31