Disjoint Sparse Table に乗るのはやはりモノイドかもしれない。

昔の記事で Disjoint Sparse Table には半群が乗るという思想を言ったのですが、使う上ではモノイドにして空の区間に対応した方が嬉しいし、そもそも実装を変えると自然に長さ の区間に対応できることに気付きました。 お騒がせして申し訳ありません。 ACL 風の実装を用意しました。

#pragma GCC target("lzcnt")

#include <algorithm>
#include <cassert>
#include <vector>

namespace noshi91 {

template <class S, S (*op)(S, S), S (*e)()> class disjoint_sparse_table {
  std::vector<std::vector<S>> t;

  int size() const { return t[0].size() - 2; }

public:
  disjoint_sparse_table(const std::vector<S> &v) : t() {
    const int n = v.size() + 2;
    const int h = 32 - __builtin_clz(n - 1);
    t.assign(h, std::vector<S>(n, e()));
    for (int k = 1; k < h; k++) {
      auto &s = t[k];
      const int w = 1 << k;
      for (int i = w; i < n; i += w * 2) {
        for (int j = i - 1; j > i - w; j--)
          s[j - 1] = op(v[j - 1], s[j]);
        const int m = std::min(i + w - 1, n - 1);
        for (int j = i; j < m; j++)
          s[j + 1] = op(s[j], v[j - 1]);
      }
    }
  }

  S get(int p) const {
    assert(0 <= p && p < size());
    return prod(p, p + 1);
  }
  
  S prod(int l, int r) const {
    assert(0 <= l && l <= r && r <= size());
    r++;
    const auto &s = t[31 - __builtin_clz(l ^ r)];
    return op(s[l], s[r]);
  }
};

} // namespace noshi91

t[0] には全て単位元が入っているのがギャグっぽいですが、意味的には自然でクエリの場合分けも消えるし、 掛かる初期化に の無駄な処理が入っていても良いだろうということで残しています。