src/lazy_segment_tree.hpp

View this file on GitHub
Last update: 2022-06-23 22:24:35+09:00
Include: #include "src/lazy_segment_tree.hpp"

Depends on

src/template.hpp

Code

// WIP
#pragma once
#include "template.hpp"

template<class Monoid>
struct LazySegmentTree {
  using T = typename Monoid::value_type;

  ll n;
  vector<T> tree;
  const Monoid ope;

  SegmentTree(ll n) : n(n) {
    tree.assign(2*n, ope.ide);
  }

  void build(const vector<T>& v) {
    rep(i, v.size())
      tree[i+n] = v[i];
    per(i, n)
      tree[i] = ope(tree[i*2], tree[i*2+1]);
  }

  void change(ll p, const T& x) {
    p += n;
    tree[p] = x;
    while (p >>= 1)
      tree[p] = ope(tree[p*2], tree[p*2+1]);
  }

  T query(ll l, ll r) const {
    T l_res{};
    T r_res{};
    for (l += n, r+= n; l < r; l >>= 1, r >>= 1) {
      if (l&1) l_res = ope(l_res, tree[l++]);
      if (r&1) r_res = ope(tree[--r], r_res);
    }
    return ope(l_res, r_res);
  }

  T operator[](ll i) {
    return tree[i+n];
  }
};

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus.py", line 187, in bundle
    bundler.update(path)
  File "/opt/hostedtoolcache/Python/3.11.3/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/cplusplus_bundle.py", line 312, in update
    raise BundleErrorAt(path, i + 1, "#pragma once found in a non-first line")
onlinejudge_verify.languages.cplusplus_bundle.BundleErrorAt: src/lazy_segment_tree.hpp: line 2: #pragma once found in a non-first line