概要
本記事では、次の形の問題を扱います。
$X$ をモノイドとして、$(x_0, \ldots, x_{N-1})$ を $X$ の元の列とする。次の形の $Q$ 個のクエリに答えよ：区間 $[a,b)$ が与えられるので、$\prod_{a\leq i < b} x_i$ を求めよ（添字昇順の総積 $x_a\cdots x_{b-1}$）。
ただし、列は静的、クエリはオフラインである。つまり、$x_i$ は問題において固定されており、クエリ $(a,b)$ は全てまとめて与えられていて、自由な順で答を求めればよい。
以下では簡単のため、すべてのクエリ区間 $[a,b)$ が $b-a\geq 2$ を満たすことを仮定します。実装によっては長さ $1$ のクエリの扱いを場合分けする必要があるため注意してください。また、特に断らない場合には、モノイドの $2$ 元の積の計算量は $O(1)$ であるとします。ただし、記事の一部ではこれが成り立たない場合にも注目します。
記事後半の、特殊ケースでの計算量改善についてこれまで見たことがなかったため、記事化しました。前半はよく知られている気がしますが、具体的な資料が思い当たらなかったのでここも解説しています。
分割統治による解法
$[a,b) \subset [L, R)$ となるすべてのクエリ $(a,b)$ に答える関数 dfs(L,R) を次のように設計することができます。
def dfs(L, R):
M = (L + R) // 2
[ a < M かつ M < b となるクエリの答を計算する ]
dfs(L, M), dfs(M, R)このうち答えの計算については、$a < M < b$ であるとき
$$\prod_{a\leq i < b} x_i = \biggl(\prod_{a\leq i < M}x_i\biggr)\biggl(\prod_{M\leq i < b}x_i\biggr)$$
であることを利用すると、
- 各 $L\leq a < M$ に対する $\prod_{a\leq i < M} x_i$
- 各 $M < b \leq R$ に対する $\prod_{M\leq i < b} x_i$
を前計算しておくことで、各クエリに対してモノイド積 $1$ 回で答を計算できます。$M$ からはじめて $L, R$ に向かって累積積を計算していくことで、この前計算は $R-L$ 回のモノイド積で計算できます。このことから、本問題はモノイド積の計算 $O(N\log N + Q)$ 回で解けることが分かります。
| モノイド積の回数 | 空間計算量 | |
| 分割統治 | $O(N\log N + Q)$ | $O(N+Q)$ |
実装例：https://judge.yosupo.jp/submission/125324
上の実装では、各 $[L,R)$ 内で計算対象となるクエリの取得のためにさらに $O(Q\log N)$ 時間かけているため、計算量は $O((N+Q)\log N)$ です。バケットソートなどを用いて適切にクエリを扱えば 計算量 $O(N\log N + Q)$ 時間にできますが、そのような実装の説明は省略します。
以降、「分割統治による解法」と言えば、このような方法を指すこととします。上の実装例から主要な部分を取り出すと次の形です。
auto calc = [&](int L, int M, int R, vector<T>& query) -> void {
static vector<int> dp(N + 1);
// 累積積の計算
dp[M] = unit;
for (int i = M; i > L; --i) dp[i - 1] = op(A[i - 1], dp[i]);
for (int i = M; i < R; ++i) dp[i + 1] = op(dp[i], A[i]);
// 答の計算
for (auto [q, a, b]: query) ANS[q] = op(dp[a], dp[b]);
};
auto dfs = [&](auto& dfs, int L, int R, vector<T>& query) -> void {
if (R - L <= 1) {
for (auto&& [q, a, b]: query) ANS[q] = A[a];
return;
}
int M = (L + R) / 2;
vector<T> query_L, query_R, other;
for (auto&& [q, a, b]: query) {
if (b <= M) query_L.emplace_back(q, a, b);
if (M <= a) query_R.emplace_back(q, a, b);
if (a < M && M < b) other.emplace_back(q, a, b);
}
calc(L, M, R, other), dfs(dfs, L, M, query_L), dfs(dfs, M, R, query_R);
};
dfs(dfs, 0, N, query);セグメント木との比較
セグメント木については、例えば 私の記事 で解説しています。分割統治による解法とセグメント木による解法を比較しましょう。
| モノイド積の回数 | 空間計算量 | |
| 分割統治 | $O(N\log N + Q)$ | $O(N + Q)$ |
| セグメント木 | $O(N + Q\log N)$ | $O(N)$ |
競技プログラミングでは、$N, Q$ のオーダーが同程度であるような状況がよくありますが、その状況において分割統治の解法、セグメント木による解法の時間・空間計算量は同程度であることが分かります。また、分割統治の解法は、列が静的かつクエリがオフラインという制約があるため、一見すると分割統治による解法には利点が少ないように見えるかもしれません。
しかし、分割統治による解法は、次のような場合には分割統治がセグメント木よりも大きく優れている可能性があります：
「モノイドの元 $2$ つの積」よりも「モノイドの元と $x_i$ の積」の方が高速に計算できる場合
分割統治による解法を振り返ると、$2$ 種のモノイド積を次の回数行っています。
- モノイドの元に $x_i$ をかける操作：$O(N\log N)$ 回
- モノイドの元 $2$ つをかける操作：$O(Q)$ 回
セグメント木による解法では、次のようになります。
- モノイドの元 $2$ つをかける操作：$O(N + Q\log N)$ 回
したがって、「任意のモノイドの元をかける操作」よりも「モノイドの元に $x_i$ をかける操作」の方が計算量が小さければ、分割統治による解法が計算量削減になりえます。例えば次のような例があります：
問題例 1 （クリックで開きます）
解答例：https://yukicoder.me/submissions/839527
問題例 2 （クリックで開きます）
disjoint sparse table との比較
disjoint sparse table （以下 DST）については noshi91 さんの記事 などを参照してください。セグメント木のときと同様に比較してみます。
| モノイド積の回数 | 空間計算量 | |
| 分割統治 | $O(N\log N + Q)$ | $O(N+Q)$ |
| DST | $O(N\log N + Q)$ | $O(N\log N)$ |
実は、分割統治による解法と DST による解法はほぼ同じです。より詳しくは、分割統治による解法で現れる左右方向への累積積をすべて前計算したものとして、DST を理解することができます。（ただし、一般的な DST の実装では、区間 $[L,R)$ を分割する位置を中点ではなく $2$ で割れる回数にするなどして、必要な前計算に bit 演算でアクセスしやすくするなどの工夫をします）
主な違いはすべての累積積をメモリに持つかどうかで、そのため DST は空間計算量が増えてしまうもののオンラインクエリ処理に対応できるという、それぞれの欠点・利点があります。
2 種のモノイド積「任意の積」「$x_i$ との積」に関する事項も、分割統治と DST には特に違いがありません。
分割統治の枝狩り
分割統治の実装に簡単な枝狩りを追加しましょう。累積積の前計算において、クエリが来る場所だけを計算するようにします。具体的な実装例としては、上に挙げた実装例ではほとんど数行追加するだけです。
auto calc = [&](int L, int M, int R, vector<T>& query) -> void {
static vector<int> dp(N + 1);
int min_a = M, max_b = M;
for (auto&& [q, a, b]: query) min_a = min(min_a, a), max_b = max(max_b, b);
// 累積積の計算
dp[M] = unit;
for (int i = M; i > min_a; --i) dp[i - 1] = op(A[i - 1], dp[i]);
for (int i = M; i < max_b; ++i) dp[i + 1] = op(dp[i], A[i]);
// 答の計算
for (auto [q, a, b]: query) ANS[q] = op(dp[a], dp[b]);
};モノイド積が遅い場合など、お手軽な定数倍高速化となります。
問題例 2 での比較（クリックで開きます）
枝狩りあり（1806ms）：https://atcoder.jp/contests/abc223/submissions/38769510
枝狩りによる計算量オーダー改善
クエリ区間に特殊な制約がある場合、枝狩りを実装した分割統治解法が計算量オーダーを改善する場合があります。
クエリ区間の長さがほとんど定数である場合
簡単のため、まずクエリ区間の長さが定数であるとします。つまり、定数 $K$ が存在してすべてのクエリ区間 $[a,b)$ に対して $b-a=K$ が成り立つとします。
この場合、前計算を行う $[L,R)$ の個数が $O(N/K)$ 個、各 $[L,R)$ に対する前計算が $O(K)$ 時間で行えるため、クエリのための前計算の累積積の計算は $O(N)$ 回になります。
| モノイド積の回数 | 空間計算量 | |
| 分割統治 | $O(N\log N + Q)$ | $O(N+Q)$ |
| 分割統治（枝狩り・特殊制約） | $O(N + Q)$ | $O(N+Q)$ |
$O(N+Q)$ 時間ということで、セグメント木や DST を用いるよりも良い計算量になっています。ただし、この場合には SWAG を用いることでも $O(N+Q)$ 時間が実現できて、 2 種のモノイド積「任意の積」「$x_i$ との積」に関する事項も含めて同様の計算量になります。
なお、簡単のため「クエリ区間の長さが定数」として計算量改善について述べましたが、同様の方法により、クエリ区間の長さの最大値・最小値の比が定数で抑えられている場合に$O(N+Q)$ 時間が達成できます。例えばある $K$ に対して、すべてのクエリ区間 $[a,b)$ が $K\leq b-a \leq 2K$ を満たす場合などです。
クエリ区間が単調である場合
クエリ区間の列 $\{[a_q, b_q)\}$ が単調であるとは、左端を取り出した列 $\{a_q\}$ と右端を取り出した列 $\{b_q\}$ がともに単調増加であることをいいます。この場合にもやはり、累積積の計算は $O(N)$ 回になります。
| モノイド積の回数 | 空間計算量 | |
| 分割統治 | $O(N\log N + Q)$ | $O(N + Q)$ |
| 分割統治（枝狩り・特殊制約） | $O(N + Q)$ | $O(N + Q)$ |
証明はちゃんと書くのが面倒なので、とりあえず以下のようなツイートやそのリプライを参照してください。
私の証明と noshi さんの証明は同じことを言っています。
累積積の計算が全体で $O(N)$ 時間になることをいうためには、各要素が累積積の計算に $O(1)$ 回しか現れないことを言えれば良さそうですが、これは成り立ちません。しかし、累積積の計算の heavy part みたいなものを適切に定義する（$N$ が $2$ べきの場合には、累積積をとる部分未満の最大 $2$ べきの長さのこととする）と、どの要素も左方向・右方向の heavy part には $1$ 度までしか現れないことが示せます。よって heavy part の長さの総和は $2N$ 以下となって、累積積をとる部分の長さの総和が $4N$ 以下であることがいえます。
$N$ が $2$ べきでない場合も、累積積をとる部分に含まれる最大の $[l, M)$ の形の子ノード区間を heavy part などと定めることで、同様の議論をすることができます。
帰納法による証明もいただきました。
実装例
問題例 1 での実装例（クリックで開きます）
枝狩りなし（$O((N\log N+Q)K)$ 時間、1050ms）：https://yukicoder.me/submissions/839527
枝狩りあり（$O((N+Q)K)$ 時間、273ms）：https://yukicoder.me/submissions/839592
