SparseTable

通过本教程，您可以快速掌握稀疏表的初始化、查询及高级操作。 以及学会各种 的高级用法

模板代码

template <typename T, auto op, std::size_t level = 25>
class SparseTable {
    using size_type = unsigned;
public:
    constexpr SparseTable(std::integral auto n) : SparseTable(n, [](auto x) {
        return T{};
    }) {}

    constexpr SparseTable(const std::ranges::range auto &container) : SparseTable(container.begin(), container.end()) {}

    template <typename Iterator>
    constexpr SparseTable(Iterator begin, Iterator end) : SparseTable(end - begin, [&](const auto &index) {
        return *(begin + index);
    }) {}

    constexpr SparseTable(std::integral auto n, auto &&mapping) : max_range(n) {
        if (max_range == 0) {
            return;
        }
        size_type log_size = max_range == 1 ? 1 : std::bit_width(max_range - 1);
        for (size_type i = 0; i < log_size; ++ i) {
            table[i].resize(max_range - (1 << i) + 1);
        }
        auto &value = table[0];
        for (size_type i = 0; i < max_range; ++ i) {
            value[i] = mapping(i);
        }
        for (size_type i = 1; i < log_size; ++ i) {
            auto &current = table[i];
            auto &previous = table[i - 1];
            size_type _ = max_range - (1 << i) + 1;
            for (size_type start = 0, end = 1 << (i - 1); start < _; ++ start, ++ end) {
                current[start] = op(previous[start], previous[end]);
            }
        }
    }

    constexpr auto size() const -> size_type {
        return max_range;
    }

    constexpr auto query_all() const -> T {
        return query(0, max_range - 1);
    }

    constexpr auto query(size_type index) const -> T {
        return table[0][index];
    }

    constexpr auto query(size_type left, size_type right) const -> T {
        size_type depth = std::bit_width((right - left) >> 1);
        return op(table[depth][left], table[depth][right - (1 << depth) + 1]);
    }

    constexpr auto min_left(size_type right, auto &&check) -> size_type {
        if (right < 0 or right >= max_range or not check(query(right))) {
            return -1;
        }
        return right == 0 ? right : binary_search(right, -1, [&](auto left) {
            return check(query(left, right));
        });
    }

    constexpr auto max_right(size_type left, auto &&check) -> size_type {
        if (left < 0 or left >= max_range or not check(query(left))) {
            return -1;
        }
        return left == max_range - 1 ? left : binary_search(left, max_range, [&](auto right) {
            return check(query(left, right));
        });
    }

    template <typename Ostream>
    friend constexpr auto operator <<(Ostream &ostream, const SparseTable &value) -> Ostream & {
        for (size_type i = 0; i < value.size(); ++ i) {
            ostream << value.query(i) << ' ';
        }
        return ostream;
    }

private:
    size_type max_range;
    std::array<std::vector<T>, level> table;
    constexpr auto binary_search(int ok, int ng, auto &&check) -> size_type {
        while (std::abs(ok - ng) > 1) {
            auto x = ok + (ng - ok) / 2;
            (check(x) ? ok : ng) = x;
        }
        return ok;
    }
};

简介

稀疏表是一种数据结构，用于高效处理 静态区间查询（如区间最值、区间和等）。通过预处理，它能在 时间内回答区间查询。

静态区间查询：区间的范围是固定的，不会在查询时变化的查询。

模板参数说明

• : 数据类型（如 int, double, struct 等）。
• : 区间合并操作的函数（需满足 可重复贡献，如 max, min, gcd, and, or 等）。
• （可选）: 预处理的最大层数（默认为 ，可处理 范围的数据）.

可重复贡献：指对于运算 , 满足 ，则对应的区间询问就是一个可重复贡献问题。

构造稀疏表

提供以下初始化方式：

通过容器初始化

std::vector<int> nums = {3, 1, 4, 1, 5};
SparseTable<int, std::ranges::min> st(nums);
// C++ 20 的 ranges 库有对应的lambda函数

通过迭代器范围

std::array<long long, 5> nums = {1, 2, 3, 4, 5};
SparseTable<long long, std::ranges::max, 19> st(nums.begin(), nums.end());
// 类似std::sort() 一样传送迭代器即可

long long nums[5] = {1, 2, 3, 4, 5};
SparseTable<long long, std::ranges::max> st(nums, nums + 5);
// 迭代器可以是普通数组的指针

通过指定大小和映射函数

SparseTable<int, std::bit_and<>()> st(n, [](auto i) {
    return i * i;
});
// 区间按位与查询 给定一个大小，然后从 0 ~ n-1 进行映射

auto op = [&](auto a, auto b) -> auto {
  return a & b;  
};
SparseTable<int, op> st(n, [](auto ...) {
    int x;
    std::cin >> x;
    return x;
});
// 你可以自己写 匿名函数 仿函数等等 传给运算函数op
// 区间按位与查询 给定一个大小，然后从 0 ~ n-1 进行映射
// 比如我不想额外创建一个数组，我就可以这样映射
// 因为没用到下标，所以可以不用写，就可以简单的用...占位

定义运算函数 op

操作函数必须满足 可重复贡献，例如：

最小值操作

constexpr auto op_min = [](auto a, auto b) {
    return std::min(a, b);
}; 

最大值操作

constexpr auto op_max = [](auto a, auto b) {
    return std::max(a, b);
};

最大公约数操作

constexpr auto op_gcd = [](auto a, auto b) {
    return std::gcd(a, b);
}; 

最大最小可以不用自己写，直接传入 std::ranges::max 或者 std::ranges::min , 因为这是Cpp内置的 函数

查询操作

单点查询

int value = st.query(2); // 获取索引 2 处的值

区间查询

int result = st.query(1, 3); // 查询区间 [left, right] 的结果

查询整个区间

int result = st.query_all();

二分边界查询

• min_left: 找到最小的左端点 left，使得 [left, right] 满足条件。

• max_right: 找到最大的右端点 right，使得 [left, right] 满足条件。

  // 示例：找到最大的右边界，使得区间 [2, right] 的值 ≤ 10
  auto check = [](int x) -> bool {
    return x <= 10;
  }; 
  auto right = st.max_right(2, check);
  // 当然可以直接将lambda写进去，不用声明

注意事项

数据范围

• 需足够大以覆盖数据规模（默认最大处理 元素）。

边界检查

• 查询时需确保 , 其中所有下标都是从 开始

库和版本

• 确保你的头文件引入所需的库，并且支持