更新题目 Buddy Bitmap：区间置位清位

题目 everpure-bitset · 修改（rev 11） · cc · 2026-10-27 00:33
body

@@ -1,11 +1,11 @@
 ## TL;DR
 
-- **题**：一棵满二叉树按层存成二维数组，每个节点一个 bit，父节点是 1 当且仅当两个子节点都是 1。实现 `clear_bits(start, length)` 和 `set_bits(start, length)`：把叶子层 `[start, start + length)` 置 0 或置 1，并修好所有祖先。开写前先问：数组哪一头是叶子、下标从 0 还是从 1 起、参数是否保证合法（题目一节的表）。
-- **下标**：第 k 层的节点 i，父节点是第 k + 1 层的 `i // 2`，两个子节点是第 k − 1 层的 `2i` 和 `2i + 1`，buddy（同一个父节点下的另一个子节点）是 `i ^ 1`（思路第 1 节）。
-- **不要一个叶子一个叶子地往根走**，要一层一层改：每层要改的是一段连续区间 `[lo, hi]`，往上一层变成 `[lo // 2, hi // 2]`，总工作量 O(length + 树高)（思路第 2、3 节，复杂度一节）。
-- **clear 一个数都不用读**：区间里每个父节点至少有一个子节点刚被清成 0，所以它一定是 0，整段直接写 0（思路第 3 节）。
-- **set 只读当前层的两个数**：照搬 clear 的写法会把只有一个子节点是 1 的父节点也写成 1（思路第 4 节）。正确做法是看区间两端：`lo` 是奇数就看左边的 buddy `lo - 1`，`hi` 是偶数就看右边的 buddy `hi + 1`，buddy 是 0 就把父区间那一头往里缩一格。区间缩空就停，到根那一层也要停，否则读 `hi + 1` 会越界（思路第 5、6 节）。
-- **提前停**：clear 要等「这一层一个 1 都没变成 0」才能停，只看父区间第一个数是不是已经是 0 就停是错的（思路第 7 节）。
-- **Follow-up**：每层压成 64 位的字，set 每层变成一次区间掩码加两次单 bit 读取。多线程下 set 读完 buddy、写父节点之前被 clear 插进来，会写出一个子节点是 0 的 1，最简单的修法是整个调用拿一把锁。找空闲叶子从根往下沿着 0 走。
+- **题**：满二叉树按层存成二维数组，父节点是 1 当且仅当两个子节点都是 1，实现 `clear_bits` / `set_bits(start, length)` 把叶子 `[start, start + length)` 置 0 或 1 并修好祖先，开写前问清叶子在哪头、下标起点、参数是否合法（题目一节的表）。
+- **下标**：第 k 层节点 i 的父节点是第 $k+1$ 层的 `i // 2`，子节点是第 $k-1$ 层的 `2i` 和 `2i + 1`，buddy 是 `i ^ 1`（思路第 1 节）。
+- **逐层改，别逐个叶子往根走**：每层改的是连续区间 `[lo, hi]`，上层变成 `[lo // 2, hi // 2]`，共 $O(\text{length} + h)$，h 是树高（思路第 2、3 节，复杂度一节）。
+- **clear 一个数都不用读**：父区间每个节点都有子节点刚清成 0，整段直接写 0（思路第 3 节）。
+- **set 只读两端的 buddy**：照搬 clear 会把只有一个孩子是 1 的父节点写成 1，要看两端：`lo` 为奇数看 `lo - 1`、`hi` 为偶数看 `hi + 1`，buddy 是 0 就把父区间那头缩一格，区间缩空或到根就停，否则读 `hi + 1` 越界（思路第 4、5、6 节）。
+- **提前停**：clear 要等这层一个 1 都没变成 0 才能停，只看父区间第一个数已是 0 就停是错的（思路第 7 节）。
+- **Follow-up**：每层压成 64 位字，set 每层是一次区间掩码加两次单 bit 读，多线程时 set 读完 buddy 后被 clear 插入会写出坏的 1、最简单是整个调用加锁，找空闲叶子从根沿 0 往下走（Follow-up 一节）。
 
 ## 题目
@@ -19,5 +19,5 @@
 ### 面试官给了什么
 
-- 一棵满二叉树（perfect binary tree），也就是每一层都排满，叶子数是 2 的幂。帖子里的叫法有 complete、full、perfect 三种，这三个英文词严格说含义不同，但从按层存、每层长度减半的给法看，指的都是每层排满的树。下文用 n 表示叶子数，h 表示 log₂ n，树一共有 h + 1 层。
+- 一棵满二叉树（perfect binary tree），也就是每一层都排满，叶子数是 2 的幂。帖子里的叫法有 complete、full、perfect 三种，这三个英文词严格说含义不同，但从按层存、每层长度减半的给法看，指的都是每层排满的树。下文用 n 表示叶子数，h 表示 $\log_2 n$，树一共有 h + 1 层。
 - 树按层存成二维数组 `bits[level][index]`，每个元素是 0 或 1。有的面试官还会给树高。2025 年那场用 Python，面试官提供一个帮助函数 `getBits()`，返回按层排好的列表。哪一头是叶子，各来源说法不一，见下面的表。
 - 不变式（invariant，指任何时候都必须成立的性质）：除叶子外，每个节点的值等于它两个子节点的值做「与」（AND），也就是两个都是 1 才是 1。调用之前树满足不变式，调用之后也必须满足。
@@ -71,5 +71,5 @@
 - **2025-01，[一亩三分地 1105722](https://www.1point3acres.com/interview/thread/1105722)，OA（online assessment，在线笔试）之后的第一场线上面试，共两轮，Python**（站方把它归为 Tech Phone Screen）。一轮是 [[q:everpure-fire-event]]，另一轮就是这道题。面试官给的就是上面那棵示例树，先要 `clear_bits`，follow-up 是 `set_bits`。发帖人提到 set 定父区间时要考虑头尾的 bit，贴的写法也是只看当前层两端的 buddy，区间变空后不提前停（思路第 6 节讲这样写在根那一层的风险）。帖子页面上站方自动生成的摘要举例说 `clear_bits(1, 3)` 之后叶子层变成 `[1,0,0,0,1,1,0,0]`，这是错的：叶子 1 到 3 本来就是 0，清零后叶子层不变，仍是 `1 0 0 0 1 1 1 1`。发帖人发帖时在等结果。
 - **2025-08，[Glassdoor，班加罗尔](https://www.glassdoor.com/Interview/Everpure-Software-Engineer-Interview-Questions-EI_IE364364.0,8_KO9,26_IP2.htm)**。算法轮考 bitbuddy tree，以二维数组给出，要 clear the bits and backtrack，也就是清零后往回更新祖先。发帖人说难点在读懂题意，解法本身只用到整数除法。结果没通过。
-- **2026-03 发帖（面试在 2026-01），[一亩三分地 1168429](https://www.1point3acres.com/interview/thread/1168429)**。三天三轮 coding：bit set、O(1) set、多线程 fire event，发帖人说都是 Pure Storage 的经典题，用 Go 写。这里的 bit set 应该就是这道题【推断】。帖子没写题面和具体追问，只提醒 follow-up 和论坛上流传的版本很不一样。
+- **2026-03 发帖（面试在 2026-01），[一亩三分地 1168429](https://www.1point3acres.com/interview/thread/1168429)**。三天三轮 coding：bit set、$O(1)$ set、多线程 fire event，发帖人说都是 Pure Storage 的经典题，用 Go 写。这里的 bit set 应该就是这道题【推断】。帖子没写题面和具体追问，只提醒 follow-up 和论坛上流传的版本很不一样。
 
 所以准备的重点是：能从暴力解顺畅地推到逐层的做法，说清 clear 为什么不用读、set 为什么只读两端，复杂度说得出推导。271461 的教训是犹豫和换方法本身就会扣分，Glassdoor 那篇的教训是先把题意问清楚。下面「思路」就按面试官引导的顺序排：先暴力，再逐层，再去掉对下一层的读取。
@@ -82,6 +82,6 @@
 
 - 第 k 层的节点 i，父节点是第 k + 1 层的 `i // 2`。例如叶子 4 和 5 的父节点都是第 1 层的节点 2。
-- 第 k 层的节点 p，两个子节点是第 k − 1 层的 `2p`（左）和 `2p + 1`（右）。
-- 节点 i 的 buddy，也就是同一个父节点下的另一个子节点，是 `i ^ 1`。`^` 是按位异或（XOR），`i ^ 1` 把 i 的最低位翻过来：偶数 i 的 buddy 是 i + 1，奇数 i 的 buddy 是 i − 1。所以 **i 是偶数就是左孩子，buddy 在右边。i 是奇数就是右孩子，buddy 在左边**。第 5 节会直接用这一条。
+- 第 k 层的节点 p，两个子节点是第 $k-1$ 层的 `2p`（左）和 `2p + 1`（右）。
+- 节点 i 的 buddy，也就是同一个父节点下的另一个子节点，是 `i ^ 1`。`^` 是按位异或（XOR），`i ^ 1` 把 i 的最低位翻过来：偶数 i 的 buddy 是 $i+1$，奇数 i 的 buddy 是 $i-1$。所以 **i 是偶数就是左孩子，buddy 在右边。i 是奇数就是右孩子，buddy 在左边**。第 5 节会直接用这一条。
 - 一层里的一段连续区间 `[lo, hi]`，它们的父节点也是一段连续区间 `[lo // 2, hi // 2]`：`i // 2` 随 i 单调不减，相邻的 i 映射到相同或相邻的父节点。
 - 只有这段父区间里的节点可能变：父区间外的父节点，两个子节点都不在 `[lo, hi]` 里，子节点没变，它自己当然不变。
@@ -123,5 +123,5 @@
 这个做法是对的，因为每个祖先最后一次被重算时，它下面落在区间里的叶子都已经改完了，所以最后的值正确。
 
-问题在于重复劳动。每个叶子都要走 h 步，总共 length × h 步。但相邻的叶子共享绝大部分祖先，叶子 4 和 5 的祖先完全相同，同一个根会被重算 length 次。测试用例一节的读写次数表数出了它比一层一层的写法多做多少。这就是 271461 发帖人说的「不要从底下一个一个追回去」。它的访问顺序还在各层之间来回跳，对 cache 不友好，第 8 节细讲。
+问题在于重复劳动。每个叶子都要走 h 步，总共 $\text{length} \times h$ 步。但相邻的叶子共享绝大部分祖先，叶子 4 和 5 的祖先完全相同，同一个根会被重算 length 次。测试用例一节的读写次数表数出了它比一层一层的写法多做多少。这就是 271461 发帖人说的「不要从底下一个一个追回去」。它的访问顺序还在各层之间来回跳，对 cache 不友好，第 8 节细讲。
 
 ### 3. 一层一层改：clear 不用读任何东西
@@ -277,5 +277,5 @@
 面试官问「哪个好、为什么」，要分两层回答。
 
-第一层是工作量。第 2 节的暴力解每个叶子走满 h 步，是 O(length × h)。一层一层是 O(length + h)。
+第一层是工作量。第 2 节的暴力解每个叶子走满 h 步，是 $O(\text{length} \times h)$。一层一层是 $O(\text{length} + h)$。
 
 但面试官可能反问：暴力解加上提前停，也就是往上走时发现某个祖先的值没变就停，它也是线性的。
@@ -305,5 +305,5 @@
 ```
 
-它是线性的：在一次 set（或 clear）里，每个节点最多从 0 变成 1（或从 1 变成 0）一次。每次往上走，除了最后停下的那一步，每一步都改变了一个节点。所以总步数不超过「叶子数 + 被改变的祖先数 + 叶子数」，而被改变的祖先都在那几段父区间里，总数是 O(length + h)。测试用例的表里，它的写次数和一层一层的做法相同，读次数多一些。271461 发帖人说的「不要追回去」，指的应该是不带提前停的那种【推断】。
+它是线性的：在一次 set（或 clear）里，每个节点最多从 0 变成 1（或从 1 变成 0）一次。每次往上走，除了最后停下的那一步，每一步都改变了一个节点。所以总步数不超过「叶子数 + 被改变的祖先数 + 叶子数」，而被改变的祖先都在那几段父区间里，总数是 $O(\text{length} + h)$。测试用例的表里，它的写次数和一层一层的做法相同，读次数多一些。271461 发帖人说的「不要追回去」，指的应该是不带提前停的那种【推断】。
 
 第二层是内存访问顺序，这正是汇总文档的答案和 226030 面试官强调的点。CPU 从内存读数据时，一次读进一整块（通常 64 字节，叫一个 cache line）放进 cache，紧接着读相邻地址就很快，跳到远处就要再等一次内存。Java、C 里 `bits[k]` 是一段连续数组：一层一层做时，每一层都是从左到右扫一段连续地址。一个叶子一个叶子做时，每个叶子都要在 h + 1 个不同的数组之间跳一圈。
@@ -350,9 +350,9 @@
 ## 复杂度
 
-**时间 O(length + h)，h = log₂ n。**推导：第 k 层处理的区间是 `[lo >> k, hi >> k]`，长度不超过 `(length - 1) / 2^k + 2`（两个数各自向下取整，差最多比真实比值多 1）。对 k 从 0 到 h 求和，第一项是等比数列，和不超过 2 × (length − 1)。第二项是 2 × (h + 1)。所以总工作量不超过 2 × length + 2 × h 左右。例如 n = 65536、从下标 0 清 64 个叶子：第 0 到第 6 层写 64 + 32 + 16 + 8 + 4 + 2 + 1 = 127 次，第 7 到第 16 层的区间都缩成 `[0, 0]`，各写 1 次，共 137 次。
-
-这已经是最优的，因为叶子层的 length 个位至少要各碰一次，所以是 Ω(length)。只改一个叶子也可能让一直到根的 h 个祖先都变（比如在全 1 的树上清一个叶子），所以也是 Ω(h)。汇总文档要求的「和要改动的 bit 数成线性」，指的应该就是这个界【推断】。
-
-**额外空间 O(1)**，原地修改。
+**时间 $O(\text{length} + h)$，$h = \log_2 n$。**推导：第 k 层处理的区间是 `[lo >> k, hi >> k]`，长度不超过 `(length - 1) / 2^k + 2`（两个数各自向下取整，差最多比真实比值多 1）。对 k 从 0 到 h 求和，第一项是等比数列，和不超过 $2 \times (\text{length} - 1)$。第二项是 $2 \times (h + 1)$。所以总工作量不超过 $2 \times \text{length} + 2 \times h$ 左右。例如 n = 65536、从下标 0 清 64 个叶子：第 0 到第 6 层写 64 + 32 + 16 + 8 + 4 + 2 + 1 = 127 次，第 7 到第 16 层的区间都缩成 `[0, 0]`，各写 1 次，共 137 次。
+
+这已经是最优的，因为叶子层的 length 个位至少要各碰一次，所以是 $\Omega(\text{length})$。只改一个叶子也可能让一直到根的 h 个祖先都变（比如在全 1 的树上清一个叶子），所以也是 $\Omega(h)$。汇总文档要求的「和要改动的 bit 数成线性」，指的应该就是这个界【推断】。
+
+**额外空间 $O(1)$**，原地修改。
 
 读的次数上，`clear_bits` 一次都不读。`set_bits` 每层最多读两个数，根那一层不读，一共不超过 2h 次。
@@ -414,5 +414,5 @@
 ### 1. 每一层压成 64 位的字
 
-题目叫 bitmap，真实系统里会把每一层压成一串 64 位的字（word）：第 w 个字存这一层下标 64w 到 64w + 63 的 bit，下标 i 在第 `i // 64` 个字的第 `i % 64` 位。
+题目叫 bitmap，真实系统里会把每一层压成一串 64 位的字（word）：第 w 个字存这一层下标 $64w$ 到 $64w + 63$ 的 bit，下标 i 在第 `i // 64` 个字的第 `i % 64` 位。
 
 这时只看 buddy 的做法几乎原样搬过来：每一层要做的是「把一段连续的 bit 全部置 0 或置 1」，加上最多两次单个 bit 的读取。连续一段置 1 可以按字来做：中间整字直接或上全 1，两头不满一个字的部分用掩码（mask）。掩码 `((1 << m) - 1) << left` 是从第 `left` 位开始的 m 个 1。置 1 用按位或 `|=`，置 0 用按位与上掩码取反 `&= ~mask`。Python 的整数没有位数上限，`~mask` 会是负数，所以再与上 64 个 1（`FULL`）截回 64 位。
@@ -469,5 +469,5 @@
 ```
 
-`prow` 是压缩后的树，`prow[k]` 是第 k 层的字列表。每层的代价是 O(区间长度 / 64 + 1) 个字操作，总共 O(length / 64 + h)。
+`prow` 是压缩后的树，`prow[k]` 是第 k 层的字列表。每层区间长度记为 m，代价是 $O(m / 64 + 1)$ 个字操作，总共 $O(\text{length} / 64 + h)$。
 
 这也是「set 不读下一层」在实际系统里值钱的地方：如果还用从下一层重算的写法，要把下一层相邻两位做与、再把 128 个子节点 bit 挤成 64 个父节点 bit，这一步「挤」没有一条普通的按位运算能完成，要好几步移位加掩码（或者用专门的位提取指令），而只看 buddy 的写法根本不需要它【推断】。
@@ -490,5 +490,5 @@
 CPython 有一把全局解释器锁（GIL），同一时刻只有一个线程在执行 Python 字节码，但它只保证单条字节码不被打断，管不了「读 buddy」和「写父节点」这两条语句之间被插入，所以 Python 里照样会坏。
 
-修法是每次调用整个放在 `with lock:` 里。这样每次调用都像单独运行一样，而第 3、5 节已经证明单独运行的调用把满足不变式的树变成满足不变式的树，所以任何时刻别的线程看到的都是一棵合法的树。代价是所有调用排队执行。每次调用只做 O(length + h) 的事，持锁时间很短。
+修法是每次调用整个放在 `with lock:` 里。这样每次调用都像单独运行一样，而第 3、5 节已经证明单独运行的调用把满足不变式的树变成满足不变式的树，所以任何时刻别的线程看到的都是一棵合法的树。代价是所有调用排队执行。每次调用只做 $O(\text{length} + h)$ 的事，持锁时间很短。
 
 面试官可能接着问能不能用更细的锁、不锁整棵树。一种做法是每层一把锁，所有调用都从下往上拿，拿到第 k + 1 层的锁之后才放第 k 层的锁，英文叫 hand-over-hand locking（也叫 lock coupling），像双手交替抓绳子，抓住下一把才松开上一把。所有调用按同一方向拿锁，不会两个线程各拿一把、互等对方而死锁。后一个调用在每一层都追不上前一个，每层看到的调用顺序相同，结果等于按这个顺序一个一个执行。收益有限：clear 每次都走到根，根那一层的锁仍是所有调用排队的地方，每次调用还要多拿放 h 次锁。这一段只是推理，没有写代码测试【推断】。
@@ -496,5 +496,5 @@
 ### 3. 找一个空闲的叶子
 
-如果 1 表示占用，分配时要找一个值为 0 的叶子。这棵树能在 O(h) 内找到：**一个节点是 0，它至少有一个子节点是 0**（否则两个子节点都是 1，按不变式它就是 1）。所以根是 0 就说明某个叶子是 0。从根往下走，每层进入一个值为 0 的子节点，走到叶子就找到了。根是 1 就说明全满。
+如果 1 表示占用，分配时要找一个值为 0 的叶子。这棵树能在 $O(h)$ 内找到：**一个节点是 0，它至少有一个子节点是 0**（否则两个子节点都是 1，按不变式它就是 1）。所以根是 0 就说明某个叶子是 0。从根往下走，每层进入一个值为 0 的子节点，走到叶子就找到了。根是 1 就说明全满。
 
 ```python
@@ -513,5 +513,5 @@
 找到后调 `set_bits(rows, i, 1)` 标成占用。
 
-如果要分配一整块对齐的 2^j 个叶子，这棵树不够用：一个节点是 0 只说明它下面「不全满」，不说明「全空」。要另建一棵「父节点是 1 当且仅当至少一个子节点是 1」的树（按位或，OR），某个第 j 层节点在这棵树里是 0，才说明它下面的块全空。这棵 OR 树上 set 和 clear 的角色正好对调：set 不用读，整段父区间直接写 1。clear 要看两端的 buddy。这部分没有写代码。
+如果要分配一整块对齐的 $2^j$ 个叶子，这棵树不够用：一个节点是 0 只说明它下面「不全满」，不说明「全空」。要另建一棵「父节点是 1 当且仅当至少一个子节点是 1」的树（按位或，OR），某个第 j 层节点在这棵树里是 0，才说明它下面的块全空。这棵 OR 树上 set 和 clear 的角色正好对调：set 不用读，整段父区间直接写 1。clear 要看两端的 buddy。这部分没有写代码。
 
 ## 英文讲法
更新题目 Buddy Bitmap：区间置位清位

body

meta
