セグメント木 (一点更新、区間取得)
(datastructure/segment-tree.hpp)

• View this file on GitHub
• Last update: 2021-04-15 20:24:09+09:00
• Include: #include "datastructure/segment-tree.hpp"

Verified with

• セグメント木 (一点更新・区間最小) (test/aoj/DSL_2_A.test.cpp)
• セグメント木 (一点加算・区間和) (test/aoj/DSL_2_B.segtree.test.cpp)

Code

#ifndef _DATASTRUCTURE_SEGMENT_TREE
#define _DATASTRUCTURE_SEGMENT_TREE
/**
 * @title セグメント木 (一点更新、区間取得)
 * 
 */
#include <cassert>
#include <vector>

template <class Monoid>
struct SegmentTree {
  typedef typename Monoid::value_t value_t;
  const Monoid monoid;
  int n; // n_以上の最小の2冪
  std::vector<value_t> data;
  SegmentTree(int n_): monoid() {
    n = 1;
    while (n < n_) n *= 2;
    data.assign(2*n-1, monoid.identity());
  }

  // k番目の値(0-indexed)をaに変更
  void update(int k, int a) { // 0-indexed
    assert(0 <= k && k < n);
    // 葉の節点
    data[k+n-1] = a;
    // 登りながら更新
    for (k = (k+n)/2; k > 0; k /= 2) {  // 1-indexed
      data[k-1] = monoid.merge(data[2*k-1], data[2*k]);
    }
  }

  value_t query(int l, int r) {  // 0-indexed, [l, r)
    assert(0 <= l && l <= r && r <= n);
    value_t vl = monoid.identity(), vr = monoid.identity();
    for (l += n, r += n; l < r; l /= 2, r /= 2) {  // 1-indexed
      if (l & 1) vl = monoid.merge(vl, data[(l++)-1]);
      if (r & 1) vr = monoid.merge(data[(--r)-1],vr);
    }
    return monoid.merge(vl, vr);
  }

  value_t operator[](const int &k) {
    return query(k, k + 1);
  }
};

#endif // _DATASTRUCTURE_SEGMENT_TREE

#line 1 "datastructure/segment-tree.hpp"


/**
 * @title セグメント木 (一点更新、区間取得)
 * 
 */
#include <cassert>
#include <vector>

template <class Monoid>
struct SegmentTree {
  typedef typename Monoid::value_t value_t;
  const Monoid monoid;
  int n; // n_以上の最小の2冪
  std::vector<value_t> data;
  SegmentTree(int n_): monoid() {
    n = 1;
    while (n < n_) n *= 2;
    data.assign(2*n-1, monoid.identity());
  }

  // k番目の値(0-indexed)をaに変更
  void update(int k, int a) { // 0-indexed
    assert(0 <= k && k < n);
    // 葉の節点
    data[k+n-1] = a;
    // 登りながら更新
    for (k = (k+n)/2; k > 0; k /= 2) {  // 1-indexed
      data[k-1] = monoid.merge(data[2*k-1], data[2*k]);
    }
  }

  value_t query(int l, int r) {  // 0-indexed, [l, r)
    assert(0 <= l && l <= r && r <= n);
    value_t vl = monoid.identity(), vr = monoid.identity();
    for (l += n, r += n; l < r; l /= 2, r /= 2) {  // 1-indexed
      if (l & 1) vl = monoid.merge(vl, data[(l++)-1]);
      if (r & 1) vr = monoid.merge(data[(--r)-1],vr);
    }
    return monoid.merge(vl, vr);
  }

  value_t operator[](const int &k) {
    return query(k, k + 1);
  }
};

Back to top page