跳轉到

Sqrt Decomposition

Sqrt decomposition 會把資料切成大小約為 sqrt(n) 的 block。常見用法有兩類：一類是把查詢離線排序，減少區間左右端點移動，也就是 Mo's algorithm；另一類是在每個 block 上維護額外資訊，讓 range update 或 query 可以整塊處理。

Mo's Algorithm

Mo's algorithm 適合處理大量離線區間查詢 [l, r]。它不直接改變查詢答案的定義，而是重新安排 query 順序，讓目前維護的區間 [L, R] 不會反覆大幅移動。

使用時需要能用以下三個操作維護目前區間：

  • add(idx)：把位置 idx 加進目前區間。
  • remove(idx)：把位置 idx 從目前區間移除。
  • answer(id)：把目前區間的答案存到第 id 個 query。

時間複雜度

  • 排序 query：O(q log q)
  • 指標移動次數：約 O((n + q) sqrt n)
  • 若 add / remove 成本是 O(f)，總成本會再乘上 O(f)

模板

C++
#include <bits/stdc++.h>
using namespace std;

class Mo {
public:
    struct Query {
        int l, r, id;
    };

    int n;
    int blockSize;
    vector<Query> queries;

    Mo(int _n, int q = 0) {
        n = _n;
        blockSize = (int)sqrt(n) + 1;
        queries.reserve(q);
    }

    void addQuery(int l, int r, int id) {
        queries.push_back({l, r, id});
    }

    template<class Add, class Remove, class Answer>
    void run(Add add, Remove remove, Answer answer) {
        sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
            int ba = a.l / blockSize;
            int bb = b.l / blockSize;

            if (ba != bb) return ba < bb;
            if (ba & 1) return a.r > b.r;
            return a.r < b.r;
        });

        int L = 0;
        int R = -1;

        for (auto& q : queries) {
            while (q.l < L) add(--L);
            while (R < q.r) add(++R);
            while (q.l > L) remove(L++);
            while (R > q.r) remove(R--);

            answer(q.id);
        }
    }
};

參考題型

  • LeetCode - Threshold Majority Queries：每個 query 要找 [l, r] 中出現次數至少為 threshold 的值。Mo's algorithm 負責維護目前區間，cnt 記錄每個值的出現次數，bucket[f] 記錄出現次數為 f 的原始值集合。

這題的 add / remove 會操作 set，所以單次成本是 O(log n)；整體複雜度約為 O((n + q) sqrt n log n)。

C++
class Solution {
public:
    vector<int> subarrayMajority(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int q = queries.size();

        vector<int> vals = nums;
        sort(vals.begin(), vals.end());
        vals.erase(unique(vals.begin(), vals.end()), vals.end());

        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            a[i] = lower_bound(vals.begin(), vals.end(), nums[i]) - vals.begin();
        }

        Mo mo(n, q);
        vector<int> threshold(q);

        for (int i = 0; i < q; ++i) {
            int l = queries[i][0];
            int r = queries[i][1];
            int t = queries[i][2];

            mo.addQuery(l, r, i);
            threshold[i] = t;
        }

        int m = vals.size();
        vector<int> cnt(m, 0);
        vector<set<int>> bucket(n + 1);
        vector<int> ans(q, -1);
        int maxf = 0;

        auto add = [&](int idx) {
            int id = a[idx];
            int oldf = cnt[id];

            if (oldf > 0) {
                bucket[oldf].erase(vals[id]);
            }

            ++cnt[id];
            int newf = cnt[id];

            bucket[newf].insert(vals[id]);
            maxf = max(maxf, newf);
        };

        auto remove = [&](int idx) {
            int id = a[idx];
            int oldf = cnt[id];

            bucket[oldf].erase(vals[id]);
            --cnt[id];

            int newf = cnt[id];
            if (newf > 0) {
                bucket[newf].insert(vals[id]);
            }

            while (maxf > 0 && bucket[maxf].empty()) {
                --maxf;
            }
        };

        auto answer = [&](int qid) {
            if (maxf < threshold[qid]) {
                ans[qid] = -1;
            } else {
                ans[qid] = *bucket[maxf].begin();
            }
        };

        mo.run(add, remove, answer);
        return ans;
    }
};

Range Add + Frequency Query

這類 sqrt decomposition 不需要離線排序，而是直接在線上處理更新與查詢。把陣列切成 block 後，完整 block 用 lazy tag 處理，邊界上的零碎位置則直接修改並重建該 block 的統計資訊。

以下模板支援：

  • rangeadd(l, r, v)：把 [l, r] 全部加上 v。
  • query(t)：查目前陣列中有多少值等於 t。

時間複雜度

  • 建立資料結構：O(n)
  • rangeadd(l, r, v)：O(sqrt n) expected
  • query(t)：O(sqrt n) expected
  • 若 query 需要掃另一個長度為 m 的陣列，整體會是 O(m sqrt n) expected

維護資訊

  • arr[i]：位置 i 在 block 內的基底值，不含該 block 的 lazy。
  • lazy[b]：第 b 個 block 整體延遲加上的值。
  • bucket[b]：第 b 個 block 內，各個基底值的出現次數。

查詢值 t 時，若某個 block 的 lazy 是 lazy[b]，實際值等於 t 的元素，在 bucket[b] 中會被記成 t - lazy[b]。

模板

C++
#include <bits/stdc++.h>
using namespace std;

using ll = long long;

class SqrtDcm {
public:
    int n, b, c;
    vector<ll> arr, lazy;
    vector<unordered_map<ll, int>> bucket;

    SqrtDcm(vector<int>& nums) {
        n = nums.size();
        b = sqrt(n) + 1;
        c = (n + b - 1) / b;

        arr.resize(n);
        lazy.assign(c, 0);
        bucket.resize(c);

        for (int i = 0; i < n; ++i) {
            arr[i] = nums[i];
        }

        for (int i = 0; i < c; ++i) {
            rebuild(i);
        }
    }

    int bl(int i) {
        return i * b;
    }

    int br(int i) {
        return min(n - 1, (i + 1) * b - 1);
    }

    void rebuild(int i) {
        bucket[i].clear();

        for (int j = bl(i); j <= br(i); ++j) {
            ++bucket[i][arr[j]];
        }
    }

    void rangeadd(int l, int r, ll v) {
        int lb = l / b;
        int rb = r / b;

        if (lb == rb) {
            for (int i = l; i <= r; ++i) {
                arr[i] += v;
            }

            rebuild(lb);
            return;
        }

        for (int i = l; i <= br(lb); ++i) {
            arr[i] += v;
        }
        rebuild(lb);

        for (int i = lb + 1; i < rb; ++i) {
            lazy[i] += v;
        }

        for (int i = bl(rb); i <= r; ++i) {
            arr[i] += v;
        }
        rebuild(rb);
    }

    int query(ll t) {
        int ans = 0;

        for (int i = 0; i < c; ++i) {
            ll raw = t - lazy[i];
            auto it = bucket[i].find(raw);

            if (it != bucket[i].end()) {
                ans += it->second;
            }
        }

        return ans;
    }
};

參考題型

  • LeetCode - Number of Pairs After Increment：nums2 需要支援區間加值，查詢時要計算有多少 pair 滿足 nums1[i] + nums2[j] = total。用 sqrt decomposition 維護 nums2 後，對每個 nums1[i] 查 total - nums1[i] 的出現次數。
C++
class Solution {
public:
    vector<int> numberOfPairs(
        vector<int>& nums1,
        vector<int>& nums2,
        vector<vector<int>>& queries
    ) {
        SqrtDcm sd(nums2);
        vector<int> ret;

        for (auto& q : queries) {
            if (q[0] == 1) {
                int l = q[1];
                int r = q[2];
                int v = q[3];

                sd.rangeadd(l, r, v);
            } else {
                int total = q[1];
                int ans = 0;

                for (int x : nums1) {
                    ans += sd.query(total - x);
                }

                ret.push_back(ans);
            }
        }

        return ret;
    }
};