2020-2021:teams:manespace:树状数组
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:manespace:树状数组 [2020/06/03 16:50] intouchables [睾♂级应用 : 维护-查询-修改区间最值] |
2020-2021:teams:manespace:树状数组 [2020/06/03 17:00] (当前版本) intouchables [区间查询] |
||
|---|---|---|---|
| 行 247: | 行 247: | ||
| ====区间查询==== | ====区间查询==== | ||
| + | 因为 $C[x]$ 表示区间 $[x-lowbit(x)+1, x]$ 的最值，所以查询 $区间(x, y)$ 的最大值，可分为如下： | ||
| + | 若$y - lowbit(y) > x $，则 $query(x,y) = max(h[y], query(x, y-lowbit(y))$ | ||
| + | 否则 $query(x,y) = max(a[y], query(x, y-1))$ | ||
| + | 复杂度 $O((logn)^2)$ ，此处不予证明 | ||
| + | |||
| + | 查询代码 | ||
| + | |||
| + | <code> | ||
| + | int query(int l, int r){ | ||
| + | int ans = 0; | ||
| + | while(l <= r){ | ||
| + | ans = max(ans, a[r]); | ||
| + | --r; | ||
| + | for(; r - lowbit(r) >= l; r -= lowbit(r)) ans = max(c[r], ans); | ||
| + | } | ||
| + | return ans; | ||
| + | } | ||
| + | </code> | ||
2020-2021/teams/manespace/树状数组.1591174216.txt.gz · 最后更改: 2020/06/03 16:50 由 intouchables
