Disjoint Sparse Table
(Data_Structure/Disjoint_Sparse_Table.hpp)

• View this file on GitHub
• Last update: 2025-10-12 18:33:33+09:00
• Include: #include "Data_Structure/Disjoint_Sparse_Table.hpp"

Outline

Monoid $M$ の静的な列 $S = (S_0, S_1, \dots, S_{N-1})$ に対する区間積を以下の高速な計算量で計算を行う.

• 前計算: $O(N \log N)$ 時間.
• 本計算: $O(1)$ 時間.

Contents

Constructer

Disjoint_Sparse_Table D(const std::vector<M> &data, const std::function<M(M, M)> op, const M unit)

• Monoid $M$ 上の静的な列 data に関する Disjoint Sparse Table を構築する.
• 引数
  • data: $M$ 上の列
  • op: $M$ における演算 $M \times M \to M; (x, y) \mapsto xy$.
  • unit: $M$ における単位元.
• 計算量:
  • data のサイズを $N$ として, $O(N \log N)$ 時間.

product

M S.product(int l, int r, bool left_close = true, bool right_close = true)

• 区間積 $S_l * S_{l+1} * \dots * S_r$ を求める.
• 引数
  • left_close: false にすると, 左端が開区間になる.
  • right_close: false にすると, 右端が開区間になる.
• 制約
  • 積を取る区間が $[0, N)$ に含まれる.
• 計算量 : $O(1)$ 時間

Depends on

• template/bitop.hpp

Verified with

• verify/yosupo_library_checker/data_structure/Static_Range_Sum.test.cpp

Code

#pragma once

#include"../template/bitop.hpp"

template<typename M>
class Disjoint_Sparse_Table {
    private:
    int n, height;
    std::vector<std::vector<M>> table;
    const std::function<M(M, M)> op;
    const M unit;

    public:
    Disjoint_Sparse_Table(const std::vector<M> &data, const std::function<M(M, M)> op, const M unit): n(data.size()), op(op), unit(unit), height(n > 0 ? ceil_log2(n) : 0) {
        table = std::vector<std::vector<M>>(height, std::vector<M>(n, unit));

        if (n == 0) { return; }

        // 初段の初期化 → data 配列をそのままコピー

        table[0] = data;

        for (int h = 1; h < height; h++) {
            // h 段目は, 2^h 個のブロックからなる.
            int shift = 1 << h;

            std::vector<M> &row = table[h];

            for (int j = 0; j < n; j += 2 * shift) {
                // 左に伸びる累積積を求める.
                int t = min(j + shift, n);
                if (t - 1 >= j) {
                    row[t - 1] = data[t - 1];
                    for (int k = t - 2; k >= j; k--) { row[k] = op(data[k], row[k + 1]); }
                }

                if (n <= t) { break; }

                // 右に伸びる累積積を求める.
                row[t] = data[t];
                int r = min(t + shift, n);
                for (int k = t + 1; k < r; k++) { row[k] = op(row[k - 1], data[k]); }
            }
        }
    }

    public:
    M product(int l, int r, bool left_close = true, bool right_close = true) const {
        if (!left_close) { l++; }
        if (!right_close) { r--; }

        if (l == r) { return table[0][l]; }
        if (l > r) { return unit; }

        int h = bit_length(l ^ r) - 1;
        return op(table[h][l], table[h][r]);
    }
};

#line 2 "Data_Structure/Disjoint_Sparse_Table.hpp"

#line 2 "template/bitop.hpp"

// 非負整数 x の bit legnth を求める.
ll bit_length(ll x) {
    if (x == 0) { return 0; }
    return (sizeof(long) * CHAR_BIT) - __builtin_clzll(x);
}

// 非負整数 x の popcount を求める.
ll popcount(ll x) { return __builtin_popcountll(x); }

// 正の整数 x に対して, floor(log2(x)) を求める.
ll floor_log2(ll x) { return bit_length(x) - 1; }

// 正の整数 x に対して, ceil(log2(x)) を求める.
ll ceil_log2(ll x) { return bit_length(x - 1); }

// x の第 k ビットを取得する
int get_bit(ll x, int k) { return (x >> k) & 1; }

// x のビット列を取得する.
// k はビット列の長さとする.
vector<int> get_bits(ll x, int k) {
    vector<int> bits(k);
    rep(i, k) {
        bits[i] = x & 1;
        x >>= 1;
    }

    return bits;
}

// x のビット列を取得する.
vector<int> get_bits(ll x) { return get_bits(x, bit_length(x)); }
#line 4 "Data_Structure/Disjoint_Sparse_Table.hpp"

template<typename M>
class Disjoint_Sparse_Table {
    private:
    int n, height;
    std::vector<std::vector<M>> table;
    const std::function<M(M, M)> op;
    const M unit;

    public:
    Disjoint_Sparse_Table(const std::vector<M> &data, const std::function<M(M, M)> op, const M unit): n(data.size()), op(op), unit(unit), height(n > 0 ? ceil_log2(n) : 0) {
        table = std::vector<std::vector<M>>(height, std::vector<M>(n, unit));

        if (n == 0) { return; }

        // 初段の初期化 → data 配列をそのままコピー

        table[0] = data;

        for (int h = 1; h < height; h++) {
            // h 段目は, 2^h 個のブロックからなる.
            int shift = 1 << h;

            std::vector<M> &row = table[h];

            for (int j = 0; j < n; j += 2 * shift) {
                // 左に伸びる累積積を求める.
                int t = min(j + shift, n);
                if (t - 1 >= j) {
                    row[t - 1] = data[t - 1];
                    for (int k = t - 2; k >= j; k--) { row[k] = op(data[k], row[k + 1]); }
                }

                if (n <= t) { break; }

                // 右に伸びる累積積を求める.
                row[t] = data[t];
                int r = min(t + shift, n);
                for (int k = t + 1; k < r; k++) { row[k] = op(row[k - 1], data[k]); }
            }
        }
    }

    public:
    M product(int l, int r, bool left_close = true, bool right_close = true) const {
        if (!left_close) { l++; }
        if (!right_close) { r--; }

        if (l == r) { return table[0][l]; }
        if (l > r) { return unit; }

        int h = bit_length(l ^ r) - 1;
        return op(table[h][l], table[h][r]);
    }
};

Back to top page