@[takeoff37808](/user/352603) 你家树状数组能维护区间最值？
by Static_int @ 2022-06-27 15:03:21
建议去学st表
by Static_int @ 2022-06-27 15:03:46
@[takeoff37808](/user/352603) 深入给你解析下树状数组的原理吧。
树状数组是通过维护前缀值来计算区间值的。比如区间和就可以通过两个前缀和相减（$1+2+3+\cdots+r-(1+2+3+\cdots+l-1)$）得到。可惜的是，最大值最小值并没有这样的性质，所以不能用树状数组维护。
另外，代码中的枚举也有很大问题。树状数组是通过把数组拆分成若干个长度为二的整数次幂的快进行储存的。如果按lz那种方式枚举，就会导致一些在区间里的块根本没有枚举到。举个例子：假设块长为 8, 4, 2, 1。那么lz代码在计算(2, 12) 这段和时，就会直接把（2, 8）这一整块忽略掉。所以还是要拆成两个前缀值来进行运算。
附 树状数组模板：
```cpp
int n, c[MAXN];
inline
int lowbit(int k) {
return k & -k;
}
inline
void add(int k, int x) {
for (int i = k; i <= n; i += lowbit(i)) c[i] += x;
}
inline
int query(int k) {
int res = 0;
for (int i = k; i; i -= lowbit(i)) res += c[i];
return res;
}
```
希望能对你有所帮助。
by Static_int @ 2022-06-27 15:19:35
@[Static_int](/user/731608) 万分感谢！
by takeoff37808 @ 2022-06-27 15:31:00
@[Static_int](/user/731608) 树状数组也是可以维护区间最值的，但时间复杂度要高一点，可以看一下[这篇博客](https://www.luogu.com.cn/blog/Chanis/super-BIT)
by westernhan @ 2023-01-19 21:29:07