library/data-structures/1d-range-queries/point-update-segment-tree.hpp

• View this file on GitHub
• Last update: 2023-01-08 15:53:16-05:00
• Include: #include "library/data-structures/1d-range-queries/point-update-segment-tree.hpp"

Verified with

• verify/yosupo/yosupo-point_add_range_sum-point-update-segment-tree.test.cpp

Code

#pragma once

template <class T>
struct SegmentTree {
  const T ID = 0;

  T comb(T a, T b) { return a + b; }

  int n;
  std::vector<T> seg;

  SegmentTree() = default;
  SegmentTree(int n) { init(n); }

  void init(int _n) {
    n = _n;
    seg.assign(2 * n, ID);
  }

  void pull(int p) { seg[p] = comb(seg[2 * p], seg[2 * p + 1]); }

  void upd(int p, T val) {
    seg[p += n] = val;
    for (p /= 2; p; p /= 2) pull(p);
  }

  void add(int p, T val) {
    seg[p += n] += val;
    for (p /= 2; p; p /= 2) pull(p);
  }

  T query(int l, int r) {
    T ra = ID, rb = ID;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) ra = comb(ra, seg[l++]);
      if (r & 1) rb = comb(seg[--r], rb);
    }
    return comb(ra, rb);
  }
};

template <class T>
struct SegmentTree {
  const T ID = 0;

  T comb(T a, T b) { return a + b; }

  int n;
  std::vector<T> seg;

  SegmentTree() = default;
  SegmentTree(int n) { init(n); }

  void init(int _n) {
    n = _n;
    seg.assign(2 * n, ID);
  }

  void pull(int p) { seg[p] = comb(seg[2 * p], seg[2 * p + 1]); }

  void upd(int p, T val) {
    seg[p += n] = val;
    for (p /= 2; p; p /= 2) pull(p);
  }

  void add(int p, T val) {
    seg[p += n] += val;
    for (p /= 2; p; p /= 2) pull(p);
  }

  T query(int l, int r) {
    T ra = ID, rb = ID;
    for (l += n, r += n + 1; l < r; l /= 2, r /= 2) {
      if (l & 1) ra = comb(ra, seg[l++]);
      if (r & 1) rb = comb(seg[--r], rb);
    }
    return comb(ra, rb);
  }
};

Back to top page