分割の意味#
分割はデータ構造ではなく、考え方です。
分割の基本的な考え方は、元のデータを適切に分割し、分割後の各ブロックで部分的な情報を前処理することによって、一般的な暴力アルゴリズムよりも優れた時間計算量を得ることです。
時間計算量#
分割の時間計算量は主に分割のブロック長に依存し、一般的には平均不等式を用いて特定の問題における最適なブロック長とそれに対応する時間計算量を求めることができます。
平衡不等式#
私たちが中学校で学んだ完全平方公式 $(x+y)^2 \ge 0$ を簡単に変形すると $x^2+y^2 \ge 2xy$ が得られます。
ここで $x = \sqrt {a}$ 、 $y = \sqrt {b}$ を代入すると $a + b \ge 2\sqrt {ab}$ $(a, b > 0)$ となり、 $a = b$ のときに等号が成り立ちます。これが平衡不等式です。
分析#
ある問題を例にとります：線分木 1
そうです、線分木のテンプレート問題ですが、分割を使っても解けますし、非常に速く動作します。
ブロック長を $s$ と設定すると、どんな [l, r] 操作でも
- $l, r$ が同じブロックにある場合、列挙： $O (s)$
- $l, r$ が異なるブロックにある場合： $l$ が属するブロックを列挙し、 $l$ が属するブロックの次から $r$ が属するブロックの前までを列挙し、 $r$ が属するブロックを列挙： $O (s + \frac {n}{s})$
合計 $m$ 回の操作がある場合、総時間計算量は $O (m (s + \frac {n}{s}))$ となります。平衡不等式を利用すると、 $s = \frac {n}{s}$ のときにこの式が最小値を取ることがわかり、つまり時間計算量が最適で、このとき $s = \sqrt {n}$ となります。
（ヒント：異なる問題に対してはブロック長 $s$ が異なる場合がありますので、具体的に分析する必要がありますが、一般的にはこの問題のような操作のブロック長は $\sqrt {n}$ になります。）
テンプレート#
先ほどの線分木の問題に対して、分割のコードを書くことができます。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n, m;
long long a[N], blk[N], b[N];
int pos[N];
int R;
void add(int l, int r, long long k)
{
if(pos[l] == pos[r])
{
for(int i = l;i <= r;i++)
a[i] += k;
blk[pos[l]] += (r - l + 1) * k;
return;
}
for(int i = l;pos[i] == pos[l];i++)
{
a[i] += k;
blk[pos[i]] += k;
}
for(int i = pos[l] + 1;i <= pos[r] - 1;i++)
{
blk[i] += R * k;
b[i] += k;
}
for(int i = r;pos[i] == pos[r];i--)
{
a[i] += k;
blk[pos[i]] += k;
}
}
long long query(int l, int r)
{
long long ans = 0;
if(pos[l] == pos[r])
{
for(int i = l;i <= r;i++)
{
ans += a[i] + b[pos[i]];
}
return ans;
}
for(int i = l;pos[i] == pos[l];i++)
{
ans += a[i] + b[pos[i]];
}
for(int i = pos[l] + 1;i <= pos[r] - 1;i++)
{
ans += blk[i];
}
for(int i = r;pos[i] == pos[r];i--)
{
ans += a[i] + b[pos[i]];
}
return ans;
}
int main()
{
clock_t c1 = clock();
#ifdef LOCAL
freopen("in.in", "r", stdin);
freopen("out.out", "w", stdout);
#endif
//------------------------------
scanf("%d%d", &n, &m);
R = sqrt(n) + 1;
for(int i = 1;i <= n;i++)
{
scanf("%lld", &a[i]);
pos[i] = i / R + 1;
blk[pos[i]] += a[i];
}
long long opt, x, y, z;
while(m--)
{
scanf("%lld", &opt);
if(opt == 1)
{
scanf("%lld%lld%lld", &x, &y, &z);
add(x, y, z);
}
else if(opt == 2)
{
scanf("%lld%lld", &x, &y);
printf("%lld\n", query(x, y));
}
}
//------------------------------
end:
cerr << "Time Used:" << clock() - c1 << "ms" << endl;
return 0;
}
ヒント：
- $pos$ 配列は各要素が属するブロックの番号を記録しています。
- $blk$ 配列は各ブロック内の実際の合計を記録しています。
- $b$ 配列は線分木の $lazytag$ のように、すでに $blk$ 配列に加算されたが、まだ元の配列に「伝播」されていない値を記録しています（ただし、ここでは伝播しなくても問題ありません。コード内では伝播していません）。
その他の問題#
単点修正 + 区間内のある数以下（以上）の個数のクエリ#
各ブロックに対して、vector を構築し、ソートすることができます。修正時には、二分探索で vector 内のその数の位置を見つけ、削除して挿入し、再度ソートします。
クエリの場合、完全なブロックであれば vector の $lower_bound$ を使って個数を確認すればよいです。