Function Content
init() 清空BIT
add(pos) 将1~pos位置加1
add(pos,val) 将1~pos位置加val
query(pos) 查询pos位置 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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

1
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;}};