2020-2021:teams:manespace:树状数组
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:树状数组 [2020/06/03 16:21] intouchables [区间修改] |
2020-2021:teams:manespace:树状数组 [2020/06/03 17:00] (当前版本) intouchables [区间查询] |
||
|---|---|---|---|
| 行 198: | 行 198: | ||
| ==线段树：我不要面子的吗== | ==线段树：我不要面子的吗== | ||
| - | 注：单次修改 <del>♪如果让你重新来过♪</del> 如果**只大不小**则复杂度 $O(log n)$，否则 $O((log n)^2)$ | + | 此处部分内容引自CSDN博主「LbyG」文章，原文链接：https://blog.csdn.net/u010598215/article/details/48206959 |
| + | |||
| ====区间修改==== | ====区间修改==== | ||
| 行 213: | 行 215: | ||
| *。。。。。。 | *。。。。。。 | ||
| - | 但 | + | 但修改 $A[i]$ 需要将所有包含 $A[i]$ 的 $C[j]$ 全部重算 |
| + | |||
| + | 可以发现，对于 $x$，可以转移到 $x$ 的只有，$x-2^0，x-2^1，x-2^2，.......，x-2^k$ （$k$ 满足$2^k < lowbit(x)$且2<sup>(k+1)</sup> $>= lowbit(x)$） | ||
| + | |||
| + | 例：$x = 1010000 (80)$ | ||
| + | |||
| + | $= 1001000 + lowbit(1001000) = 1001000 + 1000 = 1001000 + 2^3$ | ||
| + | |||
| + | $= 1001100 + lowbit(1001100) = 1001100 + 100 = 1001100 + 2^2$ | ||
| + | |||
| + | $= 1001110 + lowbit(1001110) = 1001110 + 10 = 1001110 + 2^1$ | ||
| + | |||
| + | $= 1001111 + lowbit(1001111) = 1001111 + 1 = 1001111 + 2^0$ | ||
| + | |||
| + | 所以对于每个 $C[i]$ ，重算的复杂度为 $O(logn)$，总复杂度$O((logn)^2)$ （若维护最大值且修改只大不小，则复杂度 $O(log n)$） | ||
| + | |||
| + | 与维护区间和类似的维护最值代码： | ||
| <code> | <code> | ||
| 行 224: | 行 242: | ||
| x += lb; | x += lb; | ||
| } | } | ||
| + | } | ||
| + | </code> | ||
| + | |||
| + | ====区间查询==== | ||
| + | |||
| + | 因为 $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> | </code> | ||
2020-2021/teams/manespace/树状数组.1591172471.txt.gz · 最后更改: 2020/06/03 16:21 由 intouchables
