树状数组模板

Function	Content
init()	清空BIT
add(pos)	将1~pos位置加1
add(pos,val)	将1~pos位置加val
query(pos)	查询pos位置

struct BIT{
  int t[2000006],tot;
  void init(){
    memset(t,0,sizeof(t));
    tot=0;
  }
  void add(int i,int val=1){
    tot++;
    for(;i<=len;i+=(i&-i)){
      t[i]+=val;
    }
  }
  int query(int i){
    int s=0;
    for(;i;i-=(i&-i)){
      s+=t[i];
    }
    return s;
  }
};

一~行~坨BIT

struct BIT{int t[2000006],tot;void init(){memset(t,0,sizeof(t));tot=0;}void add(int i,int val=1){tot++;for(;i<=len;i+=(i&-i)){t[i]+=val;}}int query(int i){int s=0;for(;i;i-=(i&-i)){s+=t[i];}return s;}};