2020-2021:teams:manespace:树状数组
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:树状数组 [2020/06/03 16:43] intouchables [区间查询] |
2020-2021:teams:manespace:树状数组 [2020/06/03 17:00] (当前版本) intouchables [区间查询] |
||
|---|---|---|---|
| 行 197: | 行 197: | ||
| ==线段树：我不要面子的吗== | ==线段树：我不要面子的吗== | ||
| + | |||
| + | 此处部分内容引自CSDN博主「LbyG」文章，原文链接：https://blog.csdn.net/u010598215/article/details/48206959 | ||
| 行 245: | 行 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))$ |
| - | 此应用部分以上部分内容引自CSDN博主「LbyG」文章，原文链接：https://blog.csdn.net/u010598215/article/details/48206959 | + | |
| + | 复杂度 $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/树状数组.1591173783.txt.gz · 最后更改: 2020/06/03 16:43 由 intouchables
