8
0

《树状数组》一节习题笔记(二)

2026-11-20
2026-11-20

本文记录了作者学习罗勇军《算法竞赛》中《高级数据结构》一章《树状数组》一节时,完成部分习题的笔记。

HDU 1541 - Stars

题意

平面上有 N 个点,第 i 个点的坐标为 (x_i, y_i)。定义第 i 个点的等级为横坐标小于等于 x_i 且纵坐标小于等于 y_i 的点的个数(不包含点 i 自身)。求出第 0 \sim N - 1 级分别有多少个点。

思路

简单的二维偏序。题目输入天然有序,因此不必额外排序。注意本题是多测,原题题面在这一点上表述不清。

HDU 5869 - Different GCD Subarray Query

题意

给定一个长度为 N 的正整数数组 a。有 Q 次询问,每次询问形如 (L, R),代表询问下标区间 [L, R] 中所有子数组可能产生的最大公约数(GCD)值的数量。

思路

首先考虑 GCD 的性质。如果固定右端点 R,那么在左端点不断左移时,GCD 值单调不增,且如果减少至少除以 2,也就是说 GCD 至多只有 \log_2 (\max a_i) 种结果。可以对每个右端点 i,预处理出以 i 结尾的所有 GCD 值。由于 GCD 值单调不增,每个 GCD 值必定对应一段连续区间(长度可以为 1),为避免重复统计,我们只记录这段区间的右端点,组成一个二元组 (L, v)。可以预处理出这些二元组。

我们对所有询问离线下来处理。将 R 从小到大排序。在处理到右端点 i 时,我们将其对应的所有二元组 (L, v) 做如下处理加入树状数组:

  • 若 v 值此前已经出现过:记上次出现的位置为 lst_v,在 lst_v 处减去 1(避免重复统计),在 L 处加上 1,并令 lst_v \leftarrow L;
  • 若 v 值此前没有出现过,直接在 L 处加上 1,同时记录 lst_v \leftarrow L。

这样,树状数组在每个位置 p 上的含义为:在以当前右端点 i 为结尾的子数组中,最靠右的左端点恰好是 p 的 GCD 值的种类数。

在处理到 (L, R) 时,所有左端点小于等于 R 的 GCD 值都被加入,此时直接计算 [L, R] 的区间和,也就是代码中的 sum[R] - sum[L-1]。

HDU 5057 - Argestes and Sequence

题意

给定一个长度为 N 的非负整数序列 a。执行 M 次操作。操作分为两种:

  • S X Y 代表将 a_X 的值设为 Y。
  • Q L R D P 代表询问在下标区间 [L, R] 内第 D 位(个位为第 1 位)是 P 的数的个数。

处理这些操作。

思路

一般的思路是开一个三维树状数组,三维分别代表位置、数位和数字,但这样树状数组会占到大约 40 MB。可以优化掉数位一维。具体来说,把所有询问离线下来,遍历数位 d \in [1, 10],每轮处理询问时,只处理第 d 位上的修改与查询操作。最后将存储的答案统一输出即可。

HDU 4456 - Crowd

题意

有一个 N \times N 的网格图,左上角为 (1, 1),右下角为 (N, N)。图中每一个点 (x, y) 都有一个权值 d(x, y)。定义 c(x_0, y_0, k) = \sum\limits_{\lvert x - x_0 \rvert + \lvert y - y_0 \rvert \leq k} d(x, y)。有如下两种操作合计 M 次,每次操作给定 x, y, z:

  • d(x, y) 增加 z(z 可能为负数);
  • 求当前的 c(x, y, z)。

处理这些操作。

思路

简单画图可以知道,曼哈顿距离不超过给定整数 k 的点是一个菱形(或菱形的一部分)。菱形不好处理,我们考虑把整个网格图旋转 45^{\circ},这样就可以把菱形转化为更好处理的正方形。常用的一种坐标变换是 x' = x - y + N,y' = x + y。由于 N \leq 10^4,变换后的新坐标的最大值 W \leq 2 \times 10^4,开二维 W^2 会 MLE。但我们注意到最多只有 M \leq 8 \times 10^4 次操作,所以可以将所有操作离线下来进行离散化,这样就能够存下了。注意由于要离散化,坐标应映射成数,例如 (i, j) 映射为 i \times W + j。然后用是树状数组处理即可。

支持与分享

如果这篇文章对你有帮助,欢迎分享给更多人或者给予支持!

《树状数组》一节习题笔记(二)
/2026/11/shu-zhuang-shu-zu-yi-jie-xi-ti-bi-ji-er
作者
Tiger
发布于
2026-11-20
许可协议
CC BY-NC-SA 4.0