2020-2021:teams:manespace:树状数组
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:manespace:树状数组 [2020/06/03 15:02] intouchables [再说原理] |
2020-2021:teams:manespace:树状数组 [2020/06/03 17:00] (当前版本) intouchables [区间查询] |
||
|---|---|---|---|
| 行 66: | 行 66: | ||
| *。。。。。。 | *。。。。。。 | ||
| 不难发现是有规律的： | 不难发现是有规律的： | ||
| - | $C[i] = A[$i-2^k+1$] + A[$i-2^k+2$] + ... + A[i]$ ----- $k$为 $i$ 的二进制中从最低位到高位连续零的长度 | + | $C[i] = A[i-2^k+1] + A[i-2^k+2] + ... + A[i]$ ----- $k$为 $i$ 的二进制中从最低位到高位连续零的长度 |
| 那么怎么求和呢？如 $$\sum_{i = 1}^{7} A[i]= C[7] + C[6] + C[4];$$ | 那么怎么求和呢？如 $$\sum_{i = 1}^{7} A[i]= C[7] + C[6] + C[4];$$ | ||
| 行 194: | 行 194: | ||
| https://www.luogu.com.cn/problem/P3372 | https://www.luogu.com.cn/problem/P3372 | ||
| - | =====睾♂级应用 : 查询-修改-维护区间最值===== | + | =====睾♂级应用 : 维护-查询-修改区间最值===== |
| ==线段树：我不要面子的吗== | ==线段树：我不要面子的吗== | ||
| - | 注：单次修改 <del>♪如果让你重新来过♪</del> 如果**只大不小**则复杂度 $O(log n)$，否则 $O((log n)^2)$ | + | 此处部分内容引自CSDN博主「LbyG」文章，原文链接：https://blog.csdn.net/u010598215/article/details/48206959 |
| - | 咕咕咕 | + | |
| + | |||
| + | ====区间修改==== | ||
| + | |||
| + | 既然是维护最值，那么树状数组 $C[i]$ 中保存的就是 $max(A[i-2^k+1] , A[i-2^k+2] , ... , A[i])$，如下： | ||
| + | *C[1] = A[1]; | ||
| + | *C[2] = max(A[1] , A[2]); | ||
| + | *C[3] = A[3]; | ||
| + | *C[4] = max(A[1] , A[2] , A[3] , A[4]); | ||
| + | *C[5] = A[5]; | ||
| + | *C[6] = max(A[5] , A[6]); | ||
| + | *C[7] = A[7]; | ||
| + | *C[8] = max(A[1] , A[2] , A[3] , A[4] , A[5] , A[6] , A[7] , A[8]); | ||
| + | *。。。。。。 | ||
| + | |||
| + | 但修改 $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> | ||
| + | void update(int x){ | ||
| + | int lb; | ||
| + | while(x <= n){ | ||
| + | c[x] = a[x]; | ||
| + | lb = lowbit(x); | ||
| + | for(int j = 1; j < lb; j <<= 1) c[x] = max(c[x], c[x-j]); | ||
| + | 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> | ||
2020-2021/teams/manespace/树状数组.1591167727.txt.gz · 最后更改: 2020/06/03 15:02 由 intouchables
