树状数组怎么求区间最值
时间: 2023-11-03 16:16:12 浏览: 71
树状数组可以用来维护一个序列的前缀和,从而实现快速区间查询。但是如果想要求区间最大值或最小值,需要进行一些修改。
具体做法如下:
1. 定义一个数组 $maxn$,表示每个节点的最大值。
2. 在更新某个节点的值时,同时更新其父节点的最大值。
3. 在查询区间最大值时,从右往左遍历每个节点,找到第一个其右边的兄弟节点的最大值大于等于查询区间左端点的位置,然后从该兄弟节点开始往右遍历,找到第一个其左边的兄弟节点的最大值小于等于查询区间右端点的位置。这两个位置之间的节点的最大值即为查询区间的最大值。
示例代码:
```cpp
const int N = 1e5;
int a[N], c[N], maxn[N];
void update(int x, int v) {
a[x] = v;
while (x <= N) {
c[x] += v;
maxn[x] = max(maxn[x], v);
x += x & -x;
}
}
int query(int l, int r) {
int res = INT_MIN;
for (int i = r; i >= l; ) {
if (i - (i & -i) + 1 >= l) {
res = max(res, maxn[i]);
i -= i & -i;
} else {
res = max(res, a[i]);
i--;
}
}
return res;
}
```
其中,$a$ 数组表示原始序列,$c$ 数组表示树状数组,$maxn$ 数组表示每个节点的最大值。在更新节点 $x$ 的值时,同时更新 $maxn$ 数组。在查询区间最大值时,从右往左遍历每个节点,找到第一个其右边的兄弟节点的最大值大于等于查询区间左端点的位置,然后从该兄弟节点开始往右遍历,找到第一个其左边的兄弟节点的最大值小于等于查询区间右端点的位置。这两个位置之间的节点的最大值即为查询区间的最大值。