居然最近才发现BIT是可以用来求最值的233，道理和线段树差不多，因为树状数组里每个点存储的数据范围是[i-lowbit(i)+1，i]，而任意一个区间都是可以被许多段这样的小区间所覆盖的，那么我们就可以用这些小区间的最值来更新所求区间的最值了。
1 struct max_bit 2 { 3 int s[maxn]; 4 int num; 5 void add(int x,int z) 6 { 7 for (int i=x;i<=num;i+=(i&-i)) s[i]=max(s[i],z); 8 } 9 int ask(int l,int r) 10 { 11 int tmp=-inf; 12 while (l<=r) 13 { 14 tmp=max(tmp,rain[r]); 15 for (r-=1;r-(r&-r)>=l;r-=(r&-r)) tmp=max(tmp,s[r]); 16 } 17 return tmp; 18 } 19 void clear() 20 { 21 memset(s,-0x3f,sizeof(s)); 22 } 23 }mx;
时间复杂度修改(O(nlogn))，查询O(logn)，空间复杂度O(n)，代码复杂度比ST表和线段树都要小。