IterativeSegmentTree

template <typename Segment>
struct IterativeSegmentTree {
  int n;
  std::vector<Segment> a;

  IterativeSegmentTree(int _n) : n(_n) {
    assert(n > 0);
    a.resize(2 * n);
  }
  
  template <typename M>
  IterativeSegmentTree(const std::vector<M>& v) : IterativeSegmentTree(v.size()) {
    for (int i = 0; i < n; ++i) {
      a[i + n] = Segment(v[i]);
    }
    for (int i = n - 1; i > 0; --i) {
      a[i] = a[i << 1] + a[i << 1 | 1];
    }
  }

  template <typename... Types>
  void modify(int p, Types&&... args) {
    assert(0 <= p && p < n);
    a[p += n].apply(args...);
    for (p >>= 1; p > 0; p >>= 1) {
      a[p] = a[p << 1] + a[p << 1 | 1];
    }
  }

  [[nodiscard]] Segment get(int l, int r) const {
    assert(0 <= l && l <= r && r <= n);
    Segment resl;
    Segment resr;
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) {
        resl = resl + a[l++];
      }
      if (r & 1) {
        resr = a[--r] + resr;
      }
    }
    return resl + resr;
  }
  
  [[nodiscard]] Segment getLeaf(int i) const {
    assert(0 <= i && i < n);
    return a[i + n];
  }
};