浅談分塊 - histcat

分塊含義#

分塊是一種思想，而不是一種數據結構。
分塊的基本思想是，通過對原數據的適當劃分，並在劃分後的每一個塊上預處理部分信息，從而較一般的暴力算法取得更優的時間複雜度。

時間複雜度#

分塊的時間複雜度主要取決於分塊的塊長，一般可以通過均值不等式求出某個問題下的最優塊長，以及相應的時間複雜度。

均衡不等式#

對於我們初中所學的完全平方公式 $(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}$

（tips：對於不同的題目可能塊長 $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;
}

tips:

$pos$ 陣列記錄的是每個元素所在的塊的編號
$blk$ 陣列記錄的是每個塊內實際的和
$b$ 陣列像是線段樹裡的 $lazytag$ 記錄的是已經加到 $blk$ 陣列裡的，但還沒有 “下傳” 到原陣列裡的值（但是這裡不用下傳也可以，代碼裡就沒有下傳）

其他題目#

單點修改 + 查詢區間內小於（等於）或大於（等於）某數的個數#

對於每一個塊，我們可以建立一個 vector 並排序。當修改的時候，二分查到 vector 內這個數所在的位置，erase 掉，插入然後再排序

查詢的話，不是完整塊就暴力枚舉，是完整塊用 vector 的 $lower_bound$ 查詢個數就行了