セグメント木

\(\mathbb{Z}_{\geq 0}\) の任意の非空な区間 \([L, R)\) は \begin{eqnarray}
[L, R)
=
\begin{cases}
[L, L+2^{\mathrm{lsb}(L)}) \sqcup [L+2^{\mathrm{lsb}(L)}, R) & (L+2^{\mathrm{lsb}(L)} < R) \\
[L, R-2^{\mathrm{lsb}(R)}) \sqcup [R-2^{\mathrm{lsb}(R)}, R) & (\text{otherwise})
\end{cases}
\end{eqnarray} を繰り返し適用することで、\(O(\log(R-L))\) 個の \([a2^k, (a+1)2^k)\) の形の区間の disjoint な和で書ける。

セグメント木は区間 \([a2^k, (a+1)2^k)\) に添え字 \(a+2^{\lceil \log_2{N} \rceil-k}\) を振って \(1,2,\ldots, N\) に直している。

// [L, R) を表すノードの id を返す。
int id(int L, int R) {
    int k = Integer.lowestOneBit(L ^ R);
    int a = L / k;
    return a + n / k;
}

public Semiring rangeProduct(int L, int R) {
    if (L >= R) return identity;
    int mL = L + Integer.lowestOneBit(L);
    int mR = R - Integer.lowestOneBit(R);
    if (mL != L && mL <= R) {
        return op.apply(v[id(L, mL)], rangeProduct(mL, R));
    } else {
        return op.apply(rangeProduct(L, mR), v[id(mR, R)]);
    }
}

更新

点 \(x\) を含む区間は $$[ \lfloor x / 2^e \rfloor 2^e, (\lfloor x/2^e \rfloor + 1 )2^e)$$ の形で書ける。幅2以上の区間は$$2^{k + 1}[a, a + 1) = 2^{k}[2a , 2a + 1) \sqcup 2^{k}[2a+1 , 2a + 2)$$に従って構築する。

BIT

任意の非空な区間 \((0, R]\) は $$ (0, R] =(0, R-2^{\mathrm{lsb}(R)}] \sqcup (R-2^{\mathrm{lsb}(R)}, R]$$ を繰り返し適用することで、 \(O(\log(R))\) 個の \((a-2^{\mathrm{lsb}(a)}, a]\) の形の区間の disjoint な和で書ける。

Sparse Table

任意の非空な区間 \([L,R)\) は$$[L, R) = [L, L + 2^{\mathrm{msb}(R-L)}) \cup [R-2^{\mathrm{msb}(R-L)}, R)$$より \([a, a+2^k)\) の形の2つの区間の和で書ける。

Disjoint Sparse Table

k次元セグメント木

可換な場合のみ扱う。任意の区間は \(\prod_{i=1}^{k} [a_i 2^{e_i}, (a_i+1)2^{e_i})\) の形の区間 \(O(\log(N)^{k})\) 個の非交和で書ける。

更新

1次元ずつ順番に更新すればよい 。つまり、任意の \(a, e\) について \(\prod_{i=1}^m [a_i2^{e_i}, (a_i+1)2^{e_i}) \times \prod_{i=1}^{m+1} [a_i2^{e_i}, a_i2^{e_i}+1)\) の積が列挙されている状態を \(m=0, 1, 2, \dots\) と得られる。

sparse な場合

\([N]^k\) 上に点が \(M\) \(( \ll N^k)\) 個しかない場合を考える。

区間の直積 \(\tilde A_1 × \tilde A_2 × \cdots × \tilde A_M\) について、各 \(\tilde A_i\) を \(A_1 \times A_2 \times \cdots \times A_{i-1} \times [N]^{k-(i-1)}\) に点を制限して、第 \(i\) 成分を座標圧縮したときの \(A_i\) とする。すると、\(\prod [a_i2^{e_i}, (a_i+1)2^{e_i})\) の形で表される区間の数が \(O(N^k)\) から \(O(M\log(M)^{k-1})\) になる。

fractional cascading

\(\tilde A = \tilde A_L \sqcup \tilde A_R\) のとき、適切な前計算の下、\(\tilde A_L, \tilde A_R\) における \([L, R)\) の添え字が \(\tilde A\) のそれから \(O(1)\) で得られる。従って、二分探索が \(\widetilde{[0, N)}\) における添え字を得るための一度だけで済む。

Disjoint Sparse Table

熨斗袋さんの記事を参考にした。任意の区間 \([L, R)\) は \([L, R) = [L, 2^e+2^{e-1})\sqcup[R, 2^e+2^{e-1})\) の形で書ける。\([*, 2^e+2^{e-1}) \subseteq [2^e, 2^e+2^{e-1})\)と\([2^e+2^{e-1}, *) \subseteq [2^e, 2^e+2^{e-1})\)の形の区間は\(O(N \log N)\)個しかない。

\([L, R) \subseteq [a2^e, (a+1)2^e)\) となる最小の \(e\) は
\([L, R) \subseteq \left[2^e\left\lfloor \frac{L}{2^e}\right\rfloor, 2^e\left(1+\left\lfloor \frac{L}{2^e}\right\rfloor\right)\right)\) を満たす最小の \(e\) と言い換えられるので \(R \leq 2^e\left(1+\left\lfloor \frac{L}{2^e}\right\rfloor\right)\) であればよい。\(R-1 \leq \sum_{i=0}^{e-1} 2^{i} + 2^e\left\lfloor \frac{L}{2^e}\right\rfloor\)と書き換えると最小値 \(e=\mathrm{msb}(R-1\ \mathrm{xor}\ L)+1\) が得られる。

オンラインFFT

\((xf(x))(xg(x)) \pmod {x^n}\) を計算したいのだが、\([x^i]fg\) の計算後にしか、\([x^{i+1}]f, [x^{i+1}]g\) が分からない。
\(\mathbb{P}^2\) を

• \([a2^k, (a+1)2^{k}) \times [2^k, 2^{k+1})\)
• \([2^k, 2^{k+1}) \times [a2^k, (a+1)2^{k}) \)

という区間に分割する。\([1, n]^2\) にはサイズ \(2^k \times 2^k\) の区間が \( O(n/2^k)\) 個現れる。したがって、オンラインFFTの計算量は \(O(\sum \frac{n}{2^k} k2^k ) = O(n \log(n)^2)\) である。\(i \leq j, 2^k < i \leq 2^{k+1}\) とする。\([x^{i+j}]fg\) は \(i+j \geq j + 2^k\) までに計算すればよいので、\(j\) を \(2^k\) ずつ区切って計算すればよい。online畳み込みは \(f=f_0+x^{n/2}f_1\, g=g_0+x^{n/2}g_1\)として、
\(f_0g_0, (f_0g_1+g_0f_1), f_1g_1\) の順に求めていると解釈することもできる。それぞれ、online, semi-online, offlineである。\(g\) がoffline の場合、\(g_0f_0\) は semi-online、\(g_1f_0, g_1f_1\) は offline、\(g_0f_1\) は semi-online となる。

• \(f_0, a\) が与えられるので、\(f_n = a_n\sum_{i+j < n}f_if_j\) を計算せよ(ABC)。
• \(a_i = [x^i] g(x)\prod_{j=1}^{i-1} (a_j+x)\) を求めよ(ABC)。