1 void add(int no,int num){ 2 for(int i=no;i<=n;i+=i&-i) 3 c[i]+=num; 4 }
| max[12]=max(a[12],c[12-1],c[12-2]) | ||||
| c[12] | a[12] | c[12-1] | c[12-2] | |
| lowbit | 4 | 1(元素本身) | 1 | 2 |
1 void update(int no，int num){ 2 c[no]=a[no]=num; 3 for(int i=1;i<(no&-no);i<<=1) 4 c[no]=max(c[no],c[no-i]); 5 }
倍增：sum[5]=c[4]+c[5];
1 int ask(int no){ 2 int out=0; 3 for(int i=no;i;i-=i&-i) 4 out+=c[i]; 5 return out; 6 }
3=(11)2
11=(1011)2
| max(3,11)=max(a[11],c[10],a[8],c[7],c[5],a[4],c[3]) | |||||||
| a[11] | c[10] | a[8] | c[7] | c[5] | a[4] | c[3] | |
| lowbit | 1 | 2 | / | 1 | 2 | / | 1 |
| 之后 | 1010 | 1000 | 111 | 110 | 100 | 11 | |
| 之前 | 1011 | 1010 | 1000 | 111 | 110 | 100 | 11 |
1 int ask(int l,int r){ 2 int ans=0; 3 while(r>=l) 4 { 5 ans=max(ans,a[r]); 6 r--; 7 for(;r-(r&-r)>=l;r-=r&-r) 8 ans=max(ans,h[r]); 9 } 10 return ans; 11 }
原文：https://www.cnblogs.com/intmian/p/BIT.html