"最少箭引爆气球"（LeetCode 452）如何用排序 + 贪心而非差分？
问题等价于"求最少不相交区间的数量"：每支箭能引爆一组重叠区间，最少箭数 = 最大不相交区间数。做法：按区间右端点排序，维护当前箭的"覆盖右边界"（初始为第一个区间右端点），遍历区间，若区间左端点 ≤ 当前右边界则重叠（共用一支箭，不更新）；否则需要新箭，更新右边界为该区间右端点并计数。复杂度 O(n log n)。
这个问题本质是"区间调度/贪心"，不是差分计数。关键洞察是"排序右端点 + 贪心选最早结束的区间"能最大化不相交数量。差分用于"区间覆盖计数"，而这里要求"最少箭覆盖所有区间"，是贪心问题，故用排序 + 贪心。
三维前缀和在张量统计中的递推展开与项数复杂度是什么？
三维前缀和 p[i][j][k] = 原值 + 三个方向的前缀和组合，用容斥公式：p[i][j][k] = a[i][j][k] + p[i-1][j][k] + p[i][j-1][k] + p[i][j][k-1] - p[i-1][j-1][k] - p[i-1][j][k-1] - p[i][j-1][k-1] + p[i-1][j-1][k-1]。即"加上所有奇数个维度减一的前缀，减去所有偶数个维度减一的前缀"。泛指 D 维前缀和的递推包含 2^D 项（容斥），因此三维 8 项、二维 4 项。查询一个子立方体同样用容斥，O(1) 时间。
D 维前缀和用容斥展开，项数为 2^D（每个维度选择"减一或不减"）。三维是 8 项，二维是 4 项。复杂度上，构建 O(n³)、查询 O(1)。每多一维，容斥项数翻倍，这是高维前缀和的主要代价。
为何异或前缀和与加法前缀和能用同一套哈希计数思路？
因为异或和加法都满足"区间为前缀差"的性质：加法区间和 = prefix[r] - prefix[l-1]，异或区间和 = pre[r] ^ pre[l-1]。两者都因为"减/异或是可逆的"（a - a = 0，a ^ a = 0），使得"区间值 = 前缀差"。因此"和为 K"统计 map[pre-K]，"异或为 K"统计 map[pre^K]，完全同一套哈希计数框架，只是把减换成异或。
关键是"区间值可表示为两个前缀的差"，且该差运算是可逆的。加法和异或都满足。所以"前缀 + 哈希"的范式对两者通用，只需替换运算符。这体现了"可逆前缀运算"的统一性。
二维前缀和如何 O(1) 求任意子矩阵和，边界累加公式是什么？
二维前缀和 p[i][j] 表示从 (1,1) 到 (i,j) 的矩形和，递推：p[i][j] = a[i][j] + p[i-1][j] + p[i][j-1] - p[i-1][j-1]。求子矩阵 (r1,c1) 到 (r2,c2) 的和 = p[r2][c2] - p[r1-1][c2] - p[r2][c1-1] + p[r1-1][c1-1]。用容斥（两减一加）O(1) 得到任意子矩阵和。构建 O(m×n)，查询 O(1)。
二维前缀和的核心是容斥：构建时"大矩形 = 左上两块和 - 重叠部分"，查询时"大矩形的和 - 两块 - 再补回重叠"。用 p[0][]=p[][0]=0 哨兵避免越界。这是二维"前缀和"从一维推广的经典。
// 构建二维前缀和
int[][] p = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
p[i][j] = a[i-1][j-1] + p[i-1][j] + p[i][j-1] - p[i-1][j-1];
// 查询 (r1,c1)-(r2,c2) 子矩阵和（1-based）
int sum = p[r2][c2] - p[r1-1][c2] - p[r2][c1-1] + p[r1-1][c1-1];
前缀和 + 哈希统计"子数组和为 0 / K / 给定值"的完整框架是什么？
完整框架：1) 维护前缀和 pre 和哈希表 map（记录前缀和出现次数，初始 map[0]=1）；2) 遍历数组，更新 pre；3) 累加 map[pre - target] 到答案（若统计"和为 target"）；4) 更新 map[pre]。对"和为 0"设 target=0；对"和为 K"设 target=K；对"可被 K 整除"改为统计 pre 与 pre%K 同余（用模）。这样统一框架覆盖 0 / K / 整除 / 给定值等。
核心是"区间和 = 前缀差"，用哈希统计"之前出现过多少个前缀和等于 pre - target"。目标值不同只改变"差值的定义"（减 target 或取模）。框架统一，可复用。
在"矩阵区域和查询 + 更新"场景中，差分与树状数组（BIT）如何取舍？
若只做"批量区间更新 + 最后一次性求点值"（离线），用二维差分合适：每次更新 O(1)，一次还原 O(mn)。若需要"在线任意点更新 + 在线任意子矩阵和查询"，则需要二维树状数组或线段树：每次更新/查询 O(log m × log n)。差分无法在线查询任意子矩阵和（因为还原后是点值，不是前缀和）。取舍依据是"是否需要在线查询"。
差分适合"离线批量更新求最终点值"；树状数组适合"在线更新 + 在线查询"。当两者都需要时（更新+查询交织），树状数组/线段树是唯一选择。这是"更新与查询频率"决定数据结构。
连续子数组异或和为 K（前缀 XOR + 哈希）的实现是什么？
与"和为 K"同构：用 pre[i] = pre[i-1] ^ nums[i] 表示前缀异或，子数组 [l..r] 的异或 = pre[r] ^ pre[l-1]。要统计异或为 K 的子数组，遍历时对每个 r 累加 map[pre[r] ^ K]（即之前出现过多少前缀异或等于 pre[r]^K），再更新 map[pre[r]]。初始 map[0]=1。复杂度 O(n)。
因为异或可逆（x^K^K=x），"pre[r] ^ pre[l-1] = K" 等价于 "pre[l-1] = pre[r] ^ K"，用哈希统计即可。这是"前缀 + 哈希"在异或下的直接应用，代码与加法版本几乎相同。
int countSubarraysXorK(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1);
int pre = 0, ans = 0;
for (int x : nums) {
pre ^= x;
ans += map.getOrDefault(pre ^ k, 0);
map.put(pre, map.getOrDefault(pre, 0) + 1);
}
return ans;
}
二维差分与二维前缀和的复合使用顺序（先差分后还原再前缀）是什么？
顺序是：先对二维差分数组做矩形更新（四角标记 +v/-v），然后对差分数组做一次二维前缀和（还原）得到原数组在每点的值。若需要再求"子矩阵和"，则对还原后的数组再构建一次二维前缀和。即"差分（更新）→ 前缀和（还原）→ 前缀和（查询）"。注意差分还原用"前缀和"运算，因为差分是前缀和的逆。
差分更新在差分数组上，还原用前缀和累加（一次二维前缀和把差分还原成原数组）。若还要查询子矩阵和，再对原数组做一次前缀和。顺序不可颠倒：必须先还原成点值，才能再求前缀和。
前缀和结果可能为负或很大时，哈希键如何选取？
哈希键直接用前缀和数值本身（作为 int 或 long）即可，因为哈希表支持任意整数键，负值和大值都能作为键。前缀和可能为负（负元素）或很大（int 溢出），需注意：求和用 long 避免溢出，作为键时用 Integer/Long 装箱。若值域有限（如取模后），可用数组替代哈希表。核心是"键就用前缀和值，无需特殊处理负值"。
哈希表天然支持整数键，负值、大值都没问题。唯一要注意的是累加溢出：用 long 保存前缀和。若约定"前缀和取模"（如可被 K 整除），则键是取模后的余数，可用数组桶。选取键的原则是"键能唯一标识需要比较的前缀状态"。
在流式（在线）数据中维护前缀和哈希以回答滚动查询的设计是什么？
流式场景下，数据不断到来，需要实时维护前缀和并向哈希表加入新前缀。设计：维护当前前缀和 pre 和哈希表 map（前缀和 → 出现次数或位置），每读入一个元素，更新 pre，把 pre 加入 map，并立即用 map 回答查询（如"当前前缀和减去某值是否出现过"）。滚动查询指"当前窗口内"的统计，需同步淘汰离开窗口的前缀（从 map 中删除或记录位置）。关键是增量更新 + 实时查询。
流式问题要求"每次来一个元素 O(1) 更新并回答查询"。维护前缀和哈希即可：更新 pre、插入 map、查询 pre-target。若窗口滚动还需按位置淘汰旧前缀。空间 O(n)（前缀数），时间 O(1) 每元素。
多个约束（如"和为 K 且长度为 L"）如何组合前缀结构？
对多个约束，可扩展前缀哈希的键为"组合信息"。例如"和为 K 且长度为 L"：要求 prefix[r] - prefix[l-1] = K 且 r - (l-1) = L，即 prefix[l-1] = prefix[r] - K 且 l-1 = r - L。哈希键可设为"前缀和"与"下标"的二元组，或先固定长度 L（滑动窗口），再用前缀和判断和。不同约束组合成键或分步处理。核心是"用哈希键编码所有需要匹配的条件"。
多约束时，哈希键需编码所有"由前缀决定"的信息。固定长度用滑动窗口，固定和用前缀哈希，两者叠加（先长度窗口再和）或组合键。这是"前缀结构 + 多条件"的扩展，视约束性质选择组合方式。
二维差分如何对矩形区域整体加减（四角标记法）？
对二维差分数组 d，对矩形 (r1,c1)-(r2,c2) 整体加 v，做四角标记：d[r1][c1] += v；d[r1][c2+1] -= v；d[r2+1][c1] -= v；d[r2+1][c2+1] += v。四角 O(1) 操作后，对该差分数组做一次二维前缀和即可得到每个点被加的总量。这是"一维差分两端标记"在二维的推广（容斥"两加两减"）。
四角标记的原理是容斥：为让矩形内 +v、矩形外不变，需在矩形的四个角做 +v/-v，再前缀和摊开。矩形右下角的下一个位置做 +v 抵消两次减法。这是二维差分矩形更新的标准做法。
区间合并（LeetCode 56）与差分的本质区别是什么（合并 vs 计数）？
区间合并（56）的目标是"把重叠/相邻区间合并成不相交的并集"，输出合并后的区间列表，用排序 + 贪心（按左端点排序，维护当前合并区间的右边界，重叠则扩展，否则闭合）。差分的本质是"区间覆盖计数"，输出每个点被覆盖的次数，用端点标记 + 前缀和。两者语义不同：合并关心"并集的形状"，差分关心"覆盖的层数"。因此解法不同，合并用排序贪心，差分用端点计数。
丢弃"合并"与"计数"两个语义：合并把重叠区间视为一个整体（并集），计数把每个点累计覆盖层数。合并不需计数，计数不需合并。选择依据是"要区间形态还是覆盖次数"。这是两类常见但易混淆的问题。
在有限网格上做差分时，溢出与取模如何处理？
有限网格做差分，若数值会很大（int 溢出），用 long 存储差分数组和累加结果。若结果需要取模（如模 M），需要注意：差分更新是"加减"，取模时要把负值调整为正（(x % M + M) % M），且最终还原时也要取模。若网格尺寸有限，边界标记（如 r2+1、c2+1）可能越界，需把数组开到 (n+2)×(n+2) 或跳过越界角点。溢出用 long，模数用正余数归一化。
处理要点：1) int 溢出用 long；2) 取模操作把负余数转正；3) 差分边界标记可能越界，用扩容数组或跳过。取模后还原时，前缀和累加也要取模。这些是网格差分在数值问题中的常见坑。
当区间端点极大（如 1e9）时，如何离散化后再做差分？
当区间端点极大（无法开大数组），但区间数量有限时，把所有区间的端点（l 和 r+1）收集起来排序去重，得到离散化的坐标集合。然后在这些离散化坐标上做差分（对每个区间的 l 和 r+1 在离散化后的位置做标记），最后前缀和还原。由于相邻离散点之间的覆盖层数相同，这样可以压缩空间，复杂度 O(m log m)（m 为区间数）。查询时把真实坐标映射到离散化索引。
离散化把"值域压缩"为"只保留关心的端点"，使差分数组大小 = 端点数量（O(m)）而非值域（O(1e9)）。相邻离散点之间覆盖不变，正确性保持。这是"大值域 + 有限区间"的经典处理。
网格题下标从 0 起还是 1 起对差分四角标记公式有什么影响？
下标从 1 起时，四角标记公式为 d[r1][c1]+=v, d[r2+1][c1]-=v, d[r1][c2+1]-=v, d[r2+1][c2+1]+=v，且数组需开 (n+2)×(n+2) 以容纳 r2+1、c2+1。下标从 0 起时，公式类似但"+1"边界可能越界（r2+1 = n 越界），需扩容到 (n+2) 或跳过越界角点。两种约定下公式形态一致，差异只在"边界是否越界"和"数组大小"的处理。
四角标记的"r2+1、c2+1"在两种下标约定下都会触及"下一位"，从 1 起时自然用 n+2 数组；从 0 起时需扩容或跳过。核心是保证"越界角点不越界"。公式本身不受下标起点影响，只是数组边界处理。
航班预订统计（LeetCode 1109）如何成为经典一维差分模板题？
该题要求对每个预定区间 [l, r] 增加座位数，多次区间更新后求每个航班的最终座位数。这正是"一维差分"的经典应用：对差分数组 d，每个区间 [l, r] 加 v 只需 d[l] += v，d[r+1] -= v；处理完所有预定后，对差分数组做一次前缀和扫描，即得到每个航班的最终座位数。复杂度 O(n + m)，是区间批量更新的模板题。
题目明确是"多次区间加 + 最后求点值"，是一维差分模板的典型。差分把每次区间更新从 O(len) 降到 O(1)，最后一次前缀和 O(n) 还原。识别"区间批量更新 + 一次性查询"即用差分。
前缀和结合单调结构（如前缀和 + 有序容器）如何求区间个数？
当"子数组和满足某区间条件"（如和 ≤ K 或和在 [L, R] 内）时，可用前缀和 + 有序容器（如平衡树、排序数组）统计：对每个前缀 pre[i]，统计"之前有多少前缀满足条件"（如在有序结构中二分查找 pre[i] - K 的位置）。用有序容器（TreeMap 或 Fenwick）支持插入和"统计小于某值的前缀数"，从而 O(n log n) 统计满足条件的区间个数。比单纯哈希更灵活（能处理区间条件）。
哈希只擅长"等于某值"（精确匹配），有序容器擅长"≤某值/区间"（范围查询）。当条件是"和 ≤ K"或"和 ∈ [L,R]"时，用有序容器在前缀集合中二分/统计排名。这是"前缀和 + 有序结构"扩展。
扫描线（事件排序）与差分有什么等价关系？何时选择哪种？
扫描线（事件排序）与差分在"区间覆盖/重叠计数"问题上是等价的：差分把每个区间拆成"起点 +1、终点 -1"两个事件，扫描线按坐标排序事件后逐个处理，原理相同。差分直接用数组下标 + 前缀和，适合"值域小、离散";扫描线用排序事件 + 遍历，适合"值域大、需离散化或在线处理"。当值域小可用差分数组更简单；值域大或坐标带权时用扫描线事件排序。
两者本质都是"用端点事件表示区间贡献"。差分省去排序（值域小），扫描线排序事件（值域大）。选择依据：值域小且连续用差分，值域大/离散/需在线用扫描线。会议室、拼车等"区间重叠"题两种情况皆可。
统计"平衡子数组"（0 与 1 数量相等）的前缀差技巧是什么？
把 0 视为 -1、1 视为 +1，则"0 与 1 数量相等的子数组"等价于"和为 0 的子数组"。用前缀和（把 0 当 -1），子数组 [l..r] 和为 0 当且仅当 pre[r] == pre[l-1]。用哈希表记录每个前缀和首次/最近出现位置（或计数），遍历时统计相等前缀和的对数，即平衡子数组个数。O(n)。
关键技巧是把"0 与 1 相等"转化为"和为 0"（把 0 映射为 -1）。于是问题退化为"和为 0 的子数组"，用前缀和 + 哈希统计。这是"符号编码"技巧，把计数问题转化为前缀和问题。
多区间覆盖最大值（求被覆盖最多层数）如何用差分求解？
求"被覆盖最多的层数"，把每个区间拆成起点（+1）和终点（-1），用差分数组做端点标记，然后前缀和扫描，每个位置的值就是该点被覆盖的层数，取最大值即为"被覆盖最多层数"。若值域大，改用扫描线（事件排序）或离散化。复杂度 O(n + 值域) 或 O(m log m)。
差分把"区间覆盖"转化为"每个点覆盖层数"：前缀和还原后，每点值是覆盖它的区间数。扫描求最大值即可。这是"区间覆盖计数"的经典应用，与"会议室/拼车"等"最大重叠"问题同源。
如何用二维差分处理"被多个矩形覆盖次数"的网格题？
每个矩形用二维差分四角标记（+1/-1），处理完所有矩形后，对二维差分数组做一次二维前缀和，得到每个网格点被覆盖的次数。若求"覆盖次数 ≥ k"的格子数或最大值，就在还原后统计。复杂度 O(矩形数 + 网格面积)。若网格大，用离散化或扫描线。
二维差分把"矩形覆盖"转化为"每个点覆盖次数"：四角标记 + 二维前缀和还原。这是"被多个矩形覆盖"问题的标准做法。关键是用容斥四角标记保证矩形内 +1、矩形外不变。
差分思想如何用于树上路径"对路径上所有点 +v"的树上差分？
树上差分用"点差分"或"边差分"。对"路径 u→v 上所有点 +v"，用点差分：diff[u] += v，diff[v] += v，diff[lca] -= v，diff[parent(lca)] -= v。然后从叶子向上做一次"子树和"（DFS 后序累加），每个点的值就是该点被加的总量。原理：路径贡献 = 从 u 到根 + 从 v 到根 - 两倍从 lca 到根 + lca 本身。用差分标记把 O(路径长度) 降到 O(1) 标记 + O(n) 还原。
树上差分核心是"把路径更新转化为端点标记 + 单次 DFS 还原"。点差分用 lca 和 parent(lca) 对冲，边差分用 lca 对冲。复杂度 O(n + m)（m 次更新）。这是 O(1) 标记 + O(n) 还原的树形推广。
拼车/会议室类"区间重叠计数"问题如何用差分或扫描线求解？
拼车（1109 变体）、会议室重叠等"区间重叠计数"问题，用差分或扫描线：把每个区间拆成起点事件（+1/上车）和终点事件（-1/下车），用差分数组（值域小）O(n) 差分前缀和，或扫描线排序事件后遍历，随时维护"当前重叠数"，检查是否超过容量上限。若求"某时刻最大重叠"取过程中的最大值即可。复杂度 O(n + 值域) 或 O(m log m)。
区间重叠计数的本质是"每个区间对时间轴做+1/-1"，差分或扫描线都能求"任意时刻重叠数"。拼车类还要检查"是否超容量"（重叠数 > 座位数）。扫描线更适合值域大，差分适合值域小。