树 状 数 组 入 门 教 程 引 言 在 解 题 过 程 中, 我 们 有 时 需 要 维 护 一 个 数 组 的 前 缀 和 S[i]=A[]+A[2]+...+A[i] 但 是 不 难 发 现, 如 果 我 们 修 改 了 任 意 一 个 A[i],S[i] S[i+]...S[n] 都 会 发 生 变 化 可 以 说, 每 次 修 改 A[i] 后, 调 整 前 缀 和 S 在 最 坏 情 况 下 会 需 要 O(n) 的 时 间 当 n 非 常 大 时, 程 序 会 运 行 得 非 常 缓 慢 因 此, 这 里 我 们 引 入 树 状 数 组, 它 的 修 改 与 求 和 都 是 O(logn) 的, 效 率 非 常 高 理 论 为 了 对 树 状 数 组 有 个 形 象 的 认 识, 我 们 先 看 下 面 这 张 图 如 图 所 示, 红 色 矩 形 表 示 的 数 组 C 就 是 树 状 数 组 这 里,C[i] 表 示 A[i-2 k +] 到 A[i] 的 和, 而 k 则 是 i 在 二 进 制 时 末 尾 0 的 个 数, 或 者 说 是 i 用 2 的 幂 方 和 表 示 时 的 最 小 指 数 当 然, 利 用 位 运 算, 我 们 可 以 直 接 计 算 出 2 k =i and (i xor (i-)) 或 i and (-i) 同 时, 我 们 也 不 难 发 现, 这 个 k 就 是 该 节 点 在 树 中 的 高 度, 因 而 这 个 树 的 高 度 不 会 超 过 logn 所 以, 当 我 们 修 改 A[i] 的 值 时, 可 以 从 C[i] 往 根 节 点 一 路 上 溯, 调 整 这 条 路 上 的 所 有 C 即 可, 这 个 操 作 的 复 杂 度 在 最 坏 情 况 下 就 是 树 的 高 度 即 O(logn) 另 外, 对 于 求 数 列 的 前 n 项 和, 只 需 找 到 n 以 前 的 所 有 最 大 子 树, 把 其 根 节 点 的 C 加 起 来 即 可 不 难 发 现, 这 些 子 树 的 数 目 是 n 在 二 进 制 时 的 个 数, 或 者 说 是 把 n 展 开 成 2 的 幂 方 和 时 的 项 数, 因 此, 求 和 操 作 的 复 杂 度 也 是 O(logn) 树 状 数 组 C, 其 中 C[i]=a[i-2 k +]+ +a[i](k 为 i 在 二 进 制 形 式 下 末 尾 0 的 个 数 ) 由 c 数 组 的 定 义 可 以 得 出 : c[]=a[] c[2]=a[]+a[2]=c[]+a[2] c[3]=a[3] c[4]=a[]+a[2]+a[3]+a[4]=c[2]+c[3]+a[4] c[5]=a[5] c[6]=a[5]+a[6]=c[5]+a[6]
c[7]=a[7] c[8]= a[]+a[2]+a[3]+a[4]+a[5]+a[6]+a[7]+a[8]=c[4]+c[6]+c[7]+a[8] c[6]=a[]+a[2]+ +a[6]=c[8]+c[2]+c[4]+c[5]+a[6] c 数 组 的 结 构 对 应 一 棵 树, 因 此 称 之 为 树 状 数 组 对 应 如 下 图 形 : 在 最 后, 我 们 将 给 出 一 些 树 状 数 组 的 实 现 代 码, 希 望 读 者 能 够 仔 细 体 会 其 中 的 细 节. 求 最 小 幂 2 k C++ 语 言 : int Lowbit(int t) return t & ( t ^ ( t - ) ); //end Pascal 语 言 : Function lowbit(x:longint):longint; var t:longint; t:=x and (x (xor(x-)); exit(t); // 相 当 于 lowbit:=t; 建 立 树 状 数 组 c 更 新 元 素 值 子 序 列 求 和, 都 与 2 k 有 关 所 以 令 lowbit(i)=2 k ( 其 中 k 为 i 在 二 进 制 下 未 尾 0 的 个 数 ) 其 实 lowbit(i)=2 k =i and (i xor (i-)) 以 i=6 为 例 (6)0=(00)2 Xor (6-)0=(5)0=(00)2 (00)2 And (6)0=(00)2 (000)2 2
2. 对 某 个 元 素 进 行 加 法 操 作 : 将 a[p] 的 值 加 上 一 个 值 x(x 可 正 可 负 ) C++ 语 言 : int plus(int p, int x) while(p <= maxn) //maxn 为 给 定 范 围 的 上 限 c[p] += x; p += Lowbit(p); Pascal 语 言 : procedure plus(p,x:longint); while p<=maxn do //maxn 为 给 定 范 围 的 上 限 c[p]:=c[p]+x; p:=p+lowbit(p) 譬 如, 修 改 9 这 个 值, 我 们 要 修 改 c[9] = c[00] c[9+2^0] = c[0] = c[00] c[0+2^] = c[2] = c[00] c[2+2^2] = c[6] = c[0000] 修 改 2 这 个 值, 我 们 要 修 改 c[2] = c[00] c[2+2^2] = c[6] = c[0000] c[6+2^4] = c[32] = c[00000] 依 此 类 推, 直 到 上 限 3. 求 前 p 项 和 : 统 计 a[]...a[p] 的 和 C++ 语 言 : int sum(int p) int sum = 0; while(p > 0) sum+ = c[p]; p- = Lowbit(p); return sum; Pascal 语 言 : Function sum(p:longint):longint; var s:longint; s:=0; while p>0 do s:=s+c[p]; p:=p-lowbit(p); exit(s); // 相 当 于 sum:=s; 譬 如, 求 a[]+a[2]+a[3]+ +a[2] 的 和 c[2] = c[00] c[2-2^2] = c[8] = c[000] c[8-2^3] = c[0] 所 以 a[]+a[2]+a[3]+ +a[2] 的 和 为 c[2]+c[8] 3
4. 统 计 a[x]..a[y] 的 值 调 用 以 上 的 sum 操 作 :sum[y]-sum[x-] 一 维 的 树 状 数 组 的 每 个 操 作 的 复 杂 度 都 是 O(logn) 的, 非 常 高 效 它 可 以 扩 充 为 n 维, 这 样 每 个 操 作 的 复 杂 度 就 变 成 了 O((logn)^n), 在 n 不 大 的 时 候 可 以 接 受 扩 充 的 方 法 就 是 将 原 来 改 变 和 查 询 的 函 数 中 的 一 个 循 环 改 成 嵌 套 的 n 个 循 环 在 n 维 的 c 数 组 中 操 作 要 注 意 树 状 数 组 能 处 理 的 是 下 标 为..n 的 数 组, 绝 对 不 能 出 现 下 标 为 0 的 情 况 因 为 lowbit(0)=0, 这 样 会 陷 入 死 循 环 实 战 运 用 例 给 定 n 个 数 列, 规 定 有 两 种 操 作, 一 是 修 改 某 个 元 素, 二 是 求 子 数 列 [a,b] 的 连 续 和 数 列 的 元 素 个 数 最 多 0 万 个, 询 问 操 作 最 多 0 万 次 输 入 格 式 第 一 行 2 个 整 数 n,m(n 表 示 输 入 n 个 数 列,m 表 示 有 m 个 操 作 ) 第 二 行 输 入 n 个 数 列 接 下 来 M 行, 每 行 有 三 个 数 k,a,b(k=0 表 示 求 子 数 列 [a,b] 的 和,k= 表 示 第 a 个 数 列 加 b 值 ) 输 出 格 式 输 出 若 干 行 数 字, 表 示 每 次 K=0 时 对 应 输 出 一 个 子 数 列 [a,b] 的 连 续 和 输 入 样 例 0 5 // 输 入 n 个 数 列, 有 m 个 操 作 2 3 4 5 6 7 8 9 0 // 输 入 n 个 数 5 // 第 个 数 加 上 5 0 3 // 求 数 列 到 数 列 3 的 连 续 和 为 0 4 8 // 求 数 列 4 到 数 列 8 的 连 续 和 为 30 7 5 // 第 7 个 数 加 上 5 0 4 8 // 求 数 列 4 到 数 列 8 的 连 续 和 为 35 输 出 样 例 30 35 参 考 程 序 Program treearray; const maxn=000; var c:array[..maxn]of longint; n,i,m,x,y,st,a,b:longint; function lowbit(x:longint):longint; lowbit:=((x-)xor x)and x; 4
procedure plus(p,x:longint); while p<=n do inc(c[p],x); inc(p,lowbit(p)); function sum(p:longint):longint; var s:longint; s:=0; while p>0 do inc(s,c[p]); dec(p,lowbit(p)); exit(s); Begin readln(n,m); fillchar(c,sizeof(c),0); for i:= to n do read(y); plus(i,y); for i:= to m do readln(st,a,b); if st=0 then writeln(sum(b)-sum(a-)) else plus(a,b); End. 例 2 数 星 星 Stars(ural028) 问 题 描 述 天 空 中 有 一 些 星 星, 这 些 星 星 都 在 不 同 的 位 置, 每 个 星 星 有 个 坐 标 如 果 一 个 星 星 的 左 下 方 ( 包 含 正 左 和 正 下 ) 有 k 颗 星 星, 就 说 这 颗 星 星 是 k 级 的 5
比 如, 在 上 面 的 例 图 中, 星 星 5 是 3 级 的 (,2,4 在 它 左 下 ) 星 星 2,4 是 级 的 例 图 中 有 个 0 级,2 个 级, 个 2 级, 个 3 级 的 星 编 程 任 务 给 定 星 星 的 位 置, 输 出 各 级 星 星 的 数 目 给 定 n 个 点, 定 义 每 个 点 的 等 级 是 在 该 点 左 下 方 ( 含 相 等 ) 的 点 的 数 目, 试 统 计 每 个 等 级 有 多 少 个 点 (n<=5000,0<=x,y<=32000) 输 入 格 式 第 行 一 个 整 数 N(<=N<=5000), 表 示 星 星 的 数 目 接 下 来 N 行 给 出 每 颗 星 星 的 坐 标, 两 个 整 数 X,Y(0<=X,Y<=32000) 不 会 有 星 星 重 叠 星 星 按 Y 坐 标 增 序 列 出,Y 坐 标 相 同 的 按 X 坐 标 增 序 列 出 输 出 格 式 N 行, 每 行 一 个 整 数, 分 别 是 0 级, 级,2 级 N- 级 的 星 星 的 数 目 输 入 样 例 5 5 7 3 3 5 5 输 出 样 例 2 0 算 法 分 析 相 当 经 典 的 树 状 数 组 题 目, 一 开 始 分 析 题 目 是 第 一 感 觉 是 二 维 的 树 状 数 组, 不 过 数 据 范 围 显 然 不 容 许 的 对 于 每 个 星 星 按 y 坐 标 从 小 到 大 排 序, 相 同 y 坐 标 按 x 坐 标 从 小 到 大 排 序 ( 题 目 中 数 据 已 经 有 序 ), 输 入 顺 序 已 排 好 序, 那 么 只 要 依 次 统 计 星 星 i 之 前 x 坐 标 小 于 等 于 i.x 的 星 星 有 多 少, 即 是 星 星 i 的 级 别 y 坐 标 没 用, 显 然 是 一 维 树 状 数 组 应 用, 这 样 也 就 成 了 树 状 数 组 的 模 型, 编 码 很 简 单 设 数 组 a[x] 初 始 为 0, 表 示 在 x 坐 标 处 星 星 的 个 数, 则 求 和 a[0] ~ a[x] 则 为 该 星 星 的 等 级, 逐 个 处 理 每 个 星 星 有 一 个 地 方 尤 其 要 注 意, 树 状 数 组 是 以 号 为 起 始 的, 而 且 只 能 用 号 x 可 能 为 0, 为 0 会 时 陷 入 死 循 环, 处 理 时 要 将 所 有 的 x+ ( 当 然 加 上 其 它 的 也 无 所 谓, 只 是 上 限 范 围 需 要 变 大 ), 还 有 就 是 x 的 范 围 不 能 事 先 确 定, 在 plus 的 时 候 我 直 接 加 到 了 x 取 值 范 围 的 最 大 值 6
例 3 校 门 外 的 树 (vijo448) 问 题 描 述 校 门 外 有 很 多 树, 有 苹 果 树, 香 蕉 树, 有 会 扔 石 头 的, 有 可 以 吃 掉 补 充 体 力 的 如 今 学 校 决 定 在 某 个 时 刻 在 某 一 段 种 上 一 种 树, 保 证 任 一 时 刻 不 会 出 现 两 段 相 同 种 类 的 树, 现 有 两 个 操 作 : K=, 读 入 l,r 表 示 在 l - r 之 间 种 上 的 一 种 树 K=2, 读 入 l,r 表 示 询 问 l - r 之 间 能 见 到 多 少 种 树 (l,r>0, 道 路 总 长 和 操 作 数 <=50000) 输 入 文 件 第 一 行 n,m 表 示 道 路 总 长 为 n, 共 有 m 个 操 作 接 下 来 m 行 为 m 个 操 作 输 出 文 件 对 于 每 个 k=2 输 出 一 个 答 案 输 入 输 出 样 例 tree.in 5 4 3 2 2 5 2 4 2 3 5 算 法 分 析 tree.out 2 这 题 看 起 来 和 树 状 数 组 没 什 么 关 系, 不 过 我 们 通 过 一 定 的 转 化, 可 以 利 用 树 状 数 组 很 好 地 解 决 这 个 问 题 我 们 不 妨 把 所 有 线 段 的 端 点 看 成 括 号 序 列, 即 把 询 问 的 区 间 [lq,rq] 看 成 在 横 坐 标 lq 处 的 一 个 [ 和 rq 处 的 ], 即 把 插 入 的 线 段 [li,ri] 看 成 在 横 坐 标 li 处 的 一 个 ( 和 ri 处 的 ) 稍 作 分 析, 我 们 不 难 发 现, 最 后 的 答 案 等 于 ] 左 边 ( 的 个 数 减 去 [ 左 边 ) 的 个 数 那 么 我 们 现 在 做 的 就 是 对 某 个 点 做 修 改, 对 某 个 前 缀 求 和 我 们 就 可 以 很 容 易 想 到 树 状 数 组 的 做 法 :. 建 立 两 个 树 状 数 T 和 T2, 分 别 维 护 ( 和 ) 2. 若 K=, 读 入 li,ri,plust(li,),plust2(ri,) 3. 若 K=2, 读 入 lq,rq,sumt(rq-)-sumt2(lq-) 小 结 经 过 前 面 概 念 和 例 题 的 讨 论, 我 们 应 该 体 会 到 了 树 状 数 组 的 特 点 : 程 序 短 速 度 快 ; 也 明 白 到 它 最 常 用 的 功 能 : 维 护 部 分 和 在 竞 赛 中, 如 果 我 们 采 用 树 状 数 组 处 理, 既 可 以 保 证 程 序 的 效 率, 也 可 以 大 幅 度 减 小 调 试 难 度, 为 选 手 省 下 大 量 的 时 间, 可 以 说 是 极 其 划 算 的 总 结 树 状 数 组 是 和 线 段 树 有 异 曲 同 工 的 数 据 结 构, 其 优 点 在 于 高 效, 写 起 来 很 好 写, 并 且 是 在 线 的 数 据 结 构 2 但 其 只 能 处 理 一 次 修 改 某 一 个 点 上 的 数 据, 并 不 能 有 效 处 理 一 次 修 改 一 个 区 间 的 数 据 ( 每 次 只 能 修 改 某 一 节 点 的 值 而 不 能 修 改 整 个 树 可 以 理 解 为 区 间 的 值 ) 3 能 用 树 状 数 组 的 题, 一 定 能 用 线 段 树 做, 但 能 用 线 段 树 做 的 题, 不 一 定 能 用 树 状 数 组 做 7