平方分割

概要

長さ $N$ の区間を $\sqrt N$ 個のバケットに分割すると各区間の長さは約 $\sqrt N$ になる．このように分割すると区間に対するクエリの計算量が $O(N)$ から $O(\sqrt N)$ に落とせることがある．セグメントツリーよりも計算量では劣るが実装が軽いことが多い．下の例は RMQ．

バケットの大きさをどのくらいにするのが良いかは想像がつきづらく，実験するしか無い．基本は 512 が高速か？ ## 計算量

クエリあたり $O(\sqrt N)$

実装

const int B = 512;

template <typename T>
class sqrt_decomp {
private:
    const int _size;
    T const init;
    std::vector<T> a, b;

public:
    sqrt_decomp(const int size = 0, T const &init_ = std::numeric_limits<T>::max())
        : _size(size), init(init_), a(size, init), b(size / B + 1, init) {}

    sqrt_decomp(const std::vector<T> &a, const int B = 310)
        : _size(a.size()), init(std::numeric_limits<T>::max()), a(a), b(_size / B + 1, init) {
        for (int i = 0; i < a.size(); i++) {
            b[i / B] = min(b[i / B], a[i]);
        }
    }

    int size() const { return _size; }

    T get(const int &l, const int &r) const {
        T res = std::numeric_limits<T>::max();
        int i = l;
        while (i < r) {
            if (i % B == 0 && i + B <= r) {
                res = min(res, b[i / B]);
                i += B;
            } else {
                res = min(res, a[i]);
                i++;
            }
        }
        return res;
    }

    void set(const int &p, const T &x) {
        a[p] = x, b[p / B] = init;
        int s = p / B, end = min(p - p % B + B, size());
        for (int i = p - p % B; i < end; i++) {
            b[s] = min(b[s], a[i]);
        }
    }

    std::vector<T> to_a(int l = -1, int r = -1) {
        if (l == -1) l = 0;
        if (r == -1) r = size();
        std::vector<T> res(r - l);
        for (int i = l; i < r; i++) res[i - l] = get(i, i + 1);
        return res;
    }
};

参考文献

蟻本

検証

AOJ DSL2A (Submission)