算法学习笔记：支配对

· · 算法·理论

可能更好的阅读体验。

引入

支配对通常用来解决一类点对贡献问题。具体来说，任意两个对象构成一个点对，我们做一定范围内的信息查询时，就相当于查询范围内的点对的信息并。但是这样点对的数量是 \mathcal{O}(n^2) 量级的，无法接受。

支配对优化这类问题的思想，就是只保留有效点对，通常题目中有性质使得有贡献的点对量级会得到减小。

不应把支配对视作一个套路式的 trick，而应该把它视作一种思想。支配对的做法是及其灵活而富有技巧性的，需要仔细感受。

第一类支配对

常见的题目类型，就是在树上做编号区间内的信息查询，并且这个信息与 LCA 强相关。本质不同的点对只有 $\mathcal{O}(n)$ 种，通常就是因为本质不同的 LCA 只有 $\mathcal{O}(n)$ 个。 求出这类支配对的常见套路是做 DSU On Tree，在 LCA 处统计贡献，每次遍历轻子树内的点为其中一个点 $u$，而其他子树内与 $u$ 构成点对的若干个 $v$ 只需要保留离 $u$ 最近的那些。这样每次遍历轻子树时，一个点只会贡献 $\mathcal{O}(1)$ 个点对，根据 DSU On Tree 的时间复杂度可以证明最终点对数量是 $\mathcal{O}(n\log{n})$ 量级的。 ### [P7880 \[Ynoi2006\] rldcot](https://www.luogu.com.cn/problem/P7880) :::info[题意] 给定 $n$ 个点的树，边有边权，$m$ 次询问 $l,r$，求 $\left\lvert\{dep_{\operatorname{lca}(i,j)}\mid l\leq i,j\leq r\}\right\rvert$。$1\leq n\leq 10^5$，$1\leq m\leq 5\times 10^5$。 ::: 把点对视作无序的，也就是钦定 $i\leq j$，显然不影响答案。将 $dep_{\operatorname{lca}(i,j)}$ 视作点对 $(i,j)$ 的颜色，那么询问 $l,r$ 就是在 $\text{4-side}$ 矩形数颜色。注意到我们实际上只需保证 $i\geq l,j\leq r$，多出的部分必然不合法，所以实际上是 $\text{2-side}$ 矩形数颜色。这是简单的，对 $r$ 从小到大扫描线，对 $\mathcal{O}(n)$ 种颜色离散化，每个颜色 $c$ 维护其最大的出现下标 $pos_c$，那么查询就转化成有多少颜色 $c$ 满足 $pos_c\geq l$，BIT 随便做。 于是我们可以轻松得到 $\mathcal{O}(n^2\log{n})$ 的暴力，把 $\mathcal{O}(n^2)$ 个点对全部扔进去扫描线即可。 考虑优化。思考对于同色点对 $(a,b),(c,d)$，若 $a\leq c\leq d\leq b$，我们称 $(c,d)$ **支配了** $(a,b)$，也就是说 $(a,b)$ 必然是无用的点对。因为如果一个询问区间包含了 $(a,b)$ 就必然包含 $(c,d)$，我们只是在数颜色，所以保留 $(c,d)$ 就够了。 使用 DSU On Tree 找出所有支配点对。具体来说，考虑当前的根节点 $x$，把它当作 LCA，每次进入轻子树遍历到一个点 $u$ 时，设前面已经遍历过的子树构成的点的编号集合为 $S$，对于形如 $(u,x)(x\in S)$ 的点对，我们只需保留 $x$ 最小的那个，同理对于形如 $(x,u)(x\in S)$ 的点对，我们只需保留 $x$ 最大的那个。用 `set` 维护集合 $S$，那么就相当于查询 $x$ 的前驱后继。显然每次进入轻子树遍历时每个点至多贡献 $2$ 个点对，因此点对总数是 $\mathcal{O}(n\log{n})$ 的。这部分时间复杂度为 $\mathcal{O}(n\log^2{n})$。 然后我们按照前文中的做法直接扫描线就行了。总体时间复杂度 $\mathcal{O}(n\log^2{n}+m\log{m}+m\log{n})$。 ### [P8528 \[Ynoi2003\] 铃原露露](https://www.luogu.com.cn/problem/P8528) :::info[题意] 给定 $n$ 个点的树，点有点权 $a_i$，保证 $a$ 是一个排列。$m$ 次询问 $l,r$，求有多少二元组 $(L,R)$ 满足 $l\leq L\leq R\leq r$ 且 $\forall L\leq a_x\leq a_y\leq R,L\leq a_{\operatorname{lca}(x,y)}\leq R$。 ::: 对于每个点对 $(x,y)(a_x<a_y)$，令 $z=\operatorname{lca}(x,y)$，分类讨论其会令哪些二元组 $(L,R)$ 不合法： - $a_z<a_x<a_y$：此时 $a_z+1\leq L\leq a_x,a_y\leq R\leq n$ 的二元组 $(L,R)$ 变得不合法。 - $a_x<a_z<a_y$：此时没有二元组会因为该点对变得不合法。 - $a_x<a_y<a_z$：此时 $1\leq L\leq a_x,a_y\leq R\leq a_z-1$ 的二元组 $(L,R)$ 变得不合法。 注意我们无需考虑 $a_x=a_y$ 的情况，因为显然此时不会有二元组变得不合法。 把不合法的 $(L,R)$ 的范围放到平面上视作矩形，考虑降低矩形的数量。还是 DSU On Tree，在每次进入轻子树遍历到一个点 $u$ 时，对于形如 $(x,u)$ 的点对，只需保留 $a_x$ 最大的那个，因为右端点的限制是相同的，我们当然取左端点限制最松的那个，这样可以覆盖限制更紧地矩形。对于形如 $(u,x)$ 的点对同理。所以我们还是用 `set` 维护点集，遍历到一个点 $u$ 的时候查询 $a_u$ 的前驱后继即可。这样矩形个数就被降到了 $\mathcal{O}(n\log{n})$ 级别。 接下来考虑如何统计答案。我们放到平面上考虑，每个不合法的矩形视作矩形 $+1$，询问就相当于查询矩形内 $0$ 个数。我们套路地把 $\text{4-side}$ 矩形加查分成两次 $\text{3-side}$ 矩形 $\pm 1$，用线段树维护其中一维，支持区间加、区间查询历史 $0$ 个数和。这是简单的，我们在节点上维护最小值、最小值个数，标记维护加法标记、历史和更新次数标记，每次 pushdown 或者在一个节点上给历史和标记 $+1$，只在最小值为 $0$ 上的节点操作即可。 $n,m$ 同阶，时间复杂度 $\mathcal{O}(n\log^2{n})$。 ### [P11364 \[NOIP2024\] 树上查询](https://www.luogu.com.cn/problem/P11364) :::info[题意] 给定 $n$ 个点的树，$q$ 次询问 $l,r,k$，求 $$ \max_{\substack{[l',r']\subseteq [l,r]\\r'-l'+1\geq k}}dep_{\operatorname{lca}[l',r']} $$ 其中 $\operatorname{lca}[l,r]=\operatorname{lca}(l,\cdots,r)$。$1\leq n,q\leq 5\times 10^5$，$1\leq k\leq r-l+1$。 ::: 关于区间 LCA 有经典结论： $$ dep_{\operatorname{lca}[l,r]}=\min_{i=l}^{r-1}dep_{\operatorname{lca}(i,i+1)} $$ 还是考虑有 $\mathcal{O}(n^2)$ 个区间，如何降低区间个数。令 $a_i=dep_{\operatorname{lca}(i,i+1)}$。首先特判掉 $n$ 个长度为 $1$ 的 $[u,u]$ 区间。接下来考虑对 $a$ 建出小根笛卡尔树，可以发现对于区间 $[l,r]$，其区间 LCA 就是 $l,r$ 在笛卡尔树上的 LCA 对应的节点。在本题中，被包含的区间必然会被支配，所以对于笛卡尔树上的每个点，我们取其子树对应的下标范围作为支配区间是最优的。这样又会增加最多 $n-1$ 个支配区间。于是我们就可以找出最多 $2n-1$ 个支配区间了。 接下来问题转化成：有 $\mathcal{O}(n)$ 个区间，区间有权值，每次询问区间 $[l,r]$ 和 $k$，求所有和 $[l,r]$ 的交集长度 $\geq k$ 的区间的权值最大值。 分类讨论产生贡献的区间 $[l',r']$ 和 $[l,r]$ 的关系。 首先 $l'\leq l\leq r\leq r'$ 的区间一定产生贡献，这是很显然的二维偏序的形式，$\text{2-side}$ 矩形最大值，容易用树状数组/线段树维护。 再来考虑 $l\leq l'$ 的情况。首先，此时无论是 $r'\leq r$ 还是 $r\leq r'$，都需要满足 $r'-l'+1\geq k$。而若 $l\leq l'\leq r\leq r'$，则还需要满足 $r-l'+1\geq k\Leftrightarrow l'\leq r-k+1$，若 $l\leq l'\leq r'\leq r$，则也有 $r-l'+1\geq r'-l'+1\geq k$。 因此，$r'-l'+1\geq k\land l\leq l'\leq r-k+1$ 是这种 case 下 $[l',r']$ 有贡献的**充要条件**。 于是我们可以从大到小枚举 $k$，把 $[l',r']$ 挂在 $l'$ 上，每次询问 $[l,r]$ 时查询 $[l,r-k+1]$ 的区间 $\max$ 即可。 还剩 $l'\leq l\leq r'\leq r$ 的 case，也是容易维护的二维偏序的形式。 这样我们做三次扫描线即可统计答案。时间复杂度 $\mathcal{O}((n+q)\log{n})$。 ## 第二类支配对 $\mathcal{O}(n^2)$ 个点对中产生的本质不同的贡献同样有 $\mathcal{O}(n^2)$ 种。 这类题通常是序列问题，在区间内查询对象两两产生贡献的 $\min/\max$。有两种常见的支配对形式： - 对于每个右端点 $r$，有 $\mathcal{O}(\log)$ 个 $l$ 可以和 $r$ 构成支配点对，这 $\mathcal{O}(\log)$ 个点对支配了所有的 $(1,r),(2,r),\cdots,(r-1,r)$ 点对。更具体地，我们通常考虑 $i<j<k$，$(i,k)$ 是有效点对时应当同时支配 $(i,j),(j,k)$，把条件写出来，题目性质会使得每往左跳一个 $l$，$l$ 的相关范围会减半。 - 分治，设当前子问题规模为 $n$，跨过分治中心的 $\mathcal{O}(n)$ 个点对支配了所有跨过中点的 $\mathcal{O}(n^2)$ 个点对。 ### [CF765F Souvenirs](https://codeforces.com/problemset/problem/765/F) :::info[题意] 给定长度为 $n$ 的序列 $a$，$m$ 次询问 $l,r$，求 $\min\limits_{l\leq i< j\leq r}|a_i-a_j|$。$2\leq n\leq 10^5$，$1\leq m\leq 3\times 10^5$。 ::: 看到绝对值自然想到分类讨论。接下来我们只考虑 $j<i\land a_j\geq a_i$ 的点对 $(j,i)$ 的贡献。$a_i>a_j$ 的部分把 $a$ 反转再做一遍即可。 固定右端点 $i$，考虑两个位置 $j,k$，满足 $i>j>k$。若 $(k,i)$ 有贡献，则： - $(k,i)$ 不能被 $(j,i)$ 支配，因此 $a_k-a_i<a_j-a_i\Leftrightarrow a_k<a_j$。 - $(k,i)$ 不能被 $(k,j)$ 支配，因此 $a_k-a_i<a_j-a_k\Leftrightarrow a_k<\dfrac{a_i+a_j}{2}$。 显然每次 $a_k$ 的上界至少减半，因此对于每个右端点 $i$，有贡献的左端点 $j$ 只有 $\mathcal{O}(\log{V})$ 个。需要支持找到最大的 $j<i$ 使得 $a_j\in[L,R]$，使用动态开点权值线段树容易 $\mathcal{O}(\log{V})$ 跳到下一个合法的位置上，右端点从小到大扫的同时在线段树上单点修改即可。 最后就是一个唐诗 $\text{2-side}$ 矩形内点权 $\min$，容易用 BIT 维护。时间复杂度 $\mathcal{O}(n\log^2V+m\log{m})$。 ### [CodeChef Minimum Xor On Segment](https://www.codechef.com/problems/MINXORSEG) :::info[题意] 给定长度为 $n$ 的序列 $a$。$q$ 次询问 $l,r$，求 $\min\limits_{l\leq i<j\leq r}\{a_i\oplus a_j\}$。$2\leq n\leq 2\times 10^5$，$1\leq q\leq 10^5$，$0\leq a_i<2^{30}$。 ::: 固定右端点 $i$，考虑两个位置 $j,k$，满足 $i>j>k$，刻画 $(k,i)$ 有贡献的条件：$a_k\oplus a_i<a_j\oplus a_i$ 且 $a_k\oplus a_i<a_k\oplus a_j$。 不妨考察 $a_i,a_j,a_k$ 在二进制表示下的 LCP 的后一位。首先指出，$a_i,a_j$ 必然在这一位上不同。 :::info[证明] 考虑反证。假设 $a_i,a_j$ 在这一位上相同，由 LCP 的极长性，必然有 $a_k$ 在这一位上与 $a_i,a_j$ 都不同。此时 $a_k\oplus a_i$ 在这一位上为 $1$，$a_j\oplus a_i$ 在这一位上为 $0$，说明 $(k,i)$ 被 $(j,i)$ 支配了，矛盾。$\Box

:::

其次，a_k 在这一位上必然与 a_i 相同，因为 a_k\oplus a_i 需要小于 a_k\oplus a_j。

注意到由于 a_i,a_j 在这一位上不同，所以这个 LCP 实际上也是 a_i,a_j 的 LCP。不难发现每次令 j\leftarrow k 时 LCP 至少拓展一位，因此每个右端点 i 对应的有贡献的左端点只有 \mathcal{O}(\log{V}) 个。

对 a_k 的限制相当于值域上的一段连续区间，所以同样可以用动态开点值域线段树维护找支配点对的过程。找到这 \mathcal{O}(n\log{V}) 个点对后和前面一题一样做个扫描线即可。时间复杂度 \mathcal{O}(n\log^2{V}+q\log{q})。

P9058 [Ynoi2004] rpmtdq / P9678 [ICPC 2022 Jinan R] Tree Distance

:::info[题意] 给定一棵 n 个点的有边权的无根树，q 次询问 l,r，求 \min\limits_{l\leq i<j\leq r}\operatorname{dist}(i,j)。1\leq n\leq 2\times 10^5，1\leq q\leq 10^6。 :::

树上路径相关，考虑点分治。设当前分治中心为 r，a_u=\operatorname{dist}(r,u)。考虑 i<j<k，刻画 (i,k) 有贡献的条件：首先 (i,k) 不能被 (i,j) 支配，因此 a_i+a_k<a_i+a_j\Leftrightarrow a_k<a_j，同理考虑 (j,k) 可以得到 a_i<a_j。由于对于每个 j\in[i+1,k-1] 都需要满足 a_i<a_j\land a_k<a_j，因此容易得出 (i,k) 有贡献的条件：\min\limits_{j=i+1}^{k-1}a_j>\max(a_i,a_k)。

注意一个细节，上面的推导中我们直接用 a_i+a_j 代替了 \operatorname{dist}(i,j)，实际上若 i,j 位于 r 的同一个儿子的子树中，可能会有 a_i+a_j\geq \operatorname{dist}(i,j)，但是这并不影响答案。我们无需担心 (i,j) 因为 \operatorname{dist} 变大而被其他点对支配的问题，因为在之后的时刻，必然会存在新的分治中心 r' 使得 r' 在 i,j 的路径上，也就是使得 a_i+a_j 变得恰等于 \operatorname{dist}(i,j)。

考虑如何找出这些支配点对。不妨处理出当前层内所有节点的 (p,a_p) 二元组，按照 p 排序。考虑支配点对 (i,j)，若 a_i\leq a_j，则 i 相当于 j 前面最靠近 j 的满足 a_i\leq a_j 的位置，若 a_i>a_j，则 j 相当于 i 后面最靠近 i 的满足 a_i>a_j 的位置，用单调栈扫一遍即可。设当前分治中心总节点个数为 n，则每一层分治会找出 \mathcal{O}(n) 个支配点对，总共就有 \mathcal{O}(n\log{n}) 个支配点对。

找出来之后还是直接扫描线即可。时间复杂度 \mathcal{O}(n\log^2{n}+q\log{q})，瓶颈在于每一层对二元组进行排序。

P9062 [Ynoi2002] Adaptive Hsearch&Lsearch

:::info[题意] 给定 n 个二维平面上的点 (x_i,y_i)。q 次询问 l,r，求 \min\limits_{l\leq i<j\leq r}\operatorname{dist}(p_i,p_j)。2\leq n\leq 2.5\times 10^5，1\leq q\leq 2.5\times 10^5，1\leq x_i,y_i\leq 10^8。 :::

回顾平面最近点对的期望线性做法：把所有点随机打乱，每次取当前答案 d 为边长，将平面划分为若干个 d\times d 的正方形块，枚举相邻的 3\times 3 的网格计算贡献，若答案更新则重构。

这启发我们考虑对平面网格化。考虑寻找合适量级的支配对来计算答案，初步想法是，取一个 d，将平面划分为若干个 d\times d 的正方形块，依次加入每个点，枚举相邻的 3\times 3 的网格中的点加入支配对中。但是这样单个网格内点数可能会很多，从而使得支配对数量达到 \mathcal{O}(n^2) 级别。

因此考虑降低单个网格内的点数。我们智慧地考虑倍增，取底数 d，设 V=\max\limits_{i=1}^n\{\max(x_i,y_i)\}，枚举 0\leq k\leq\lceil\log_dV\rceil，把平面划分为若干 d^k\times d^k 的正方形块，依次加入每个点 i，枚举相邻的 3\times 3 的网格中的点加入支配对中，然后删去和点 i 距离 <d^{k-1} 的点。

为什么这样是对的呢？沿用支配对的思路，考察下标 i<j<k，如果 (i,k) 是有贡献的支配点对，那么对于每个 i<j<k 都会有 \operatorname{dist}(p_i,p_j)>\operatorname{dist}(p_i,p_k)。考虑最小的 x 使得 d^{x-1}<\operatorname{dist}(p_i,p_k)\leq d^x，此时对于每个 i<j<k 都有 \operatorname{dist}(p_i,p_j)>d^{x-1}，因此在倍增到 d^x 时，我们依次加入下标在 [i+1,k-1] 中的点之后，p_i 必然不会被删除，同时因为 \operatorname{dist}(p_i,p_k)\leq d^x，p_i,p_k 必然在相邻的网格中，所以在枚举 p_k 的相邻网格时，(i,k) 一定会被加入支配点对中。

这里注意细节，枚举 k 时上界要取到 \lceil\log_dV\rceil，因为要保证对于每个支配点对的 \operatorname{dist} 存在一个 d^x 使得这个 \operatorname{dist} 能被枚举到，如果 k 只取到 \lfloor \log_dV\rfloor 是有可能漏枚举一些支配点对的。

还有一个细节就是，k=0 时 d^{k-1} 应该定义为 1，如果定义为 0 就会导致 n 个点重合时被卡成 \mathcal{O}(n^2)。

我们发现删去和当前点距离 <d^{k-1} 的点，可以保证每个网格中任意两点距离 \geq d^{k-1}。我们指出，这样每个网格中点的数量是 \mathcal{O}(d^2) 量级的。

:::info[证明] 这里给出一个很粗略的上界，实际上界应当比这个上界更紧。

考虑用若干个半径为 \dfrac{d^{k-1}}{2} 的圆覆盖这个 d^k\times d^k 的正方形，满足圆之间不交，从面积的角度计算，那么显然圆的个数不超过

\frac{d^k\times d^k}{\pi (\frac{d^{k-1}}{2})^2}=\frac{4d^2}{\pi}=\mathcal{O}(d^2)\quad\Box

:::

于是每轮倍增每个点会贡献 \mathcal{O}(d^2) 个支配点对，因此总支配对个数是 \mathcal{O}(nd^2\log_d V) 级别的，可以接受。

找出点对后扫描线即可。由于点对个数较多，我们扫描线时用 \mathcal{O}(1)-\mathcal{O}(\sqrt{n}) 分块平衡复杂度会更快，时间复杂度为 \mathcal{O}(nd^2\log_d V+q\sqrt{n})。我的实现下，取 d=2 跑得最快。

P8078 [WC2022] 秃子酋长 / P11367 [Ynoi2024] 魔法少女网站第二部

:::info[题意] 给定长度为 n 的排列 a，m 次询问 l,r，求 a[l,r] 中的元素排序后相邻的数在原序列中的位置的差的绝对值之和。弱化版 1\leq n,m\leq 5\times 10^5，强化版 1\leq n,m\leq 2\times 10^6。 :::

问题可以看作按照值从小到大的顺序走，求走的总步数。用链表支持 \mathcal{O}(1) 删除，套用回滚莫队即可轻松做到 \mathcal{O}(m\sqrt{n})。轻微卡常即可通过弱化版。

猫树分治，设当前分治区间为 [l,r]，分治中心为 mid=\left\lfloor\dfrac{l+r}{2}\right\rfloor，每次处理所有跨过 mid 的询问。我们尝试拆开 [l,mid] 和 [mid+1,r] 对询问的贡献。对于询问区间 [x,y]，考虑 a[x,mid] 中排序后相邻的两个元素 a_i,a_j，可以发现：

右区间 a[mid+1,y] 的贡献是类似的，若左区间有夹在 a_i,a_j 中间的数，则贡献为 i+j，否则为 |i-j|。

注意考虑边界情况，以左区间为例，考虑 a[x,mid] 中的最小值 a_i，若存在 k\in[mid+1,y] 使得 a_k<a_i，则 i 本身会有 -i 的贡献，否则贡献为 0；同样要考虑最大值 a_j，若存在 k\in[mid+1,y] 使得 a_j<a_k，则 j 会有 -j 的贡献，否则贡献为 0。

我们发现这样设计贡献可以精准地刻画询问区间的答案。为什么呢？还是以左区间为例，考虑排序后相邻的两个元素 a_i,a_j，设右区间中夹在 a_i,a_j 中间的数从小到大依次为 a_{p_1},a_{p_2},\cdots,a_{p_m}，那么：

接下来以左区间为例，考虑进一步刻画贡献条件。使用支配对思想，对于左区间中的一个相邻对 (i,j)，考虑右区间中最小的 k 使得 a_i<a_k<a_j，不难发现贡献条件变成：若询问区间的右端点 y\geq k 则贡献为 -i-j，否则贡献为 |i-j|。改写成更容易维护的形式，就是初始时就给 (i,j) 赋上 |i-j| 的贡献，若 y\geq k 就会有 -|i-j|-i-j 的增量，那么我们只需要在询问时计算总的增量。

不难发现贡献条件是一维数点的形式，考虑对询问的左端点扫描线。如果对左端点从大到小扫描线，我们要支持插入数的同时动态维护前驱后继，需要使用 set 一类的数据结构维护前驱后继，会成为时间复杂度的瓶颈。

受根号做法的启发，我们倒着做，考虑对左端点从小到大扫描线，初始状态就是对 a[l,mid] 排序，然后使用双指针对每个相邻点对 (i,j) 求出对应的 k。使用归并排序即可线性合并两个分治子区间对应的有序序列。删除一个数 a_i 时，考虑当前 a_i 的前驱后继 a_{prv},a_{nxt}，我们要把点对 (prv,i),(i,nxt) 合并成 (prv,nxt)。注意到合并得到的 (prv,nxt) 对应的 k 是容易计算的，其实就是 (prv,i),(i,nxt) 对应的 k 取 \min。然后可以使用链表支持 \mathcal{O}(1) 删除/查询前驱后继，用 BIT 维护动态一维数点，每次删数时只会更改 \mathcal{O}(1) 个位置的增量。这样我们就可以 \mathcal{O}(\log{n}) 回答一个询问，在每一层以 \mathcal{O}(n\log{n}) 的代价做扫描线，整体时间复杂度是 \mathcal{O}(n\log^2{n}+m\log{n}) 的。

注意到两边时间复杂度并不平衡，可以考虑多叉线段树。设分叉数为 t，则修改复杂度是 \mathcal{O}(\log_t{n}) 的，询问复杂度是 \mathcal{O}(t\log_t{n}) 的，要做到平衡就需要 n\log{n}\log_t{n}=mt\log_t{n}，n,m 同阶，因此解得 t=\log{n}，得到更优的理论时间复杂度 \mathcal{O}\left(\dfrac{n\log^2{n}}{\log\log{n}}\right)。但是这个一脸常数很大的样子，感觉跑不过 BIT，我没写。

关于卡常，我 TLE 了一发之后就卡过去了。优化的地方是：不要使用同一个 BIT 维护左右的贡献，应当对于左区间开一个前缀 BIT，对于右区间开一个后缀 BIT，这样询问的时候就只会调用 query 一次，可以优化掉 \dfrac{1}{2} 的常数。