lazy_segtree.cc

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

template<typename T, typename Func>
class lazy_segtree {
  struct node{
    int l, r;
    T val;
    T delayed;
  };

  int n;
  std::vector<node> dat;
  T init_val;
  Func op;

  public:
  lazy_segtree(): n(0) {}
  lazy_segtree(int n, T init_val, const Func &op): op(op), init_val(init_val) {
    int p = 1;
    while (p < n) p <<= 1;
    this->n = n = p;
    dat = std::vector<node>(p*2-1);
    for (int i=0; i<n; i++) {
      dat[n + i - 1].l = i;
      dat[n + i - 1].r = i;
      dat[n + i - 1].val = init_val;
      dat[n + i - 1].delayed = init_val;
    }
    for (int i=n-1; i>=0; i--) {
      dat[i].l = dat[2*i+1].l;
      dat[i].r = dat[2*i+2].r;
      dat[i].val = init_val;
      dat[i].delayed = init_val;
    }
  }

  //void update(int i, T val) {
  //  dat[n + i -1].val = val;
  //  int j = n + i - 1;
  //  while (j > 0) {
  //    j = (j-1)/2;
  //    dat[j].val = op(dat[2*j+1].val, dat[2*j+2].val);
  //  }
  //}

  void update_interval(int i, int j, T val) {
    update_interval(i, j, 0, val);
  }

  T query(int x, int y) {
    return query(x, y, 0);
  }

  private:
  T times(int n, const T &rhs) {
    T acc = init_val;
    for (int i = 0; i < n; i++)
      acc = op(acc, rhs);
    return acc;
  }

  void update_interval(int x, int y, int c, const T &val) {
    node &cur = dat[c];

    if (x == cur.l && y == cur.r) {
      cur.delayed = op(cur.delayed, val);
      return;
    }

    cur.val = op(cur.val, times(y - x + 1, val));
    if (x >= cur.l && y <= dat[2*c+1].r) {
      update_interval(x, y, 2*c+1, val);
      return;
    }

    if (y <= cur.r && x >= dat[2*c+2].l) {
      update_interval(x, y, 2*c+2, val);
      return;
    }

    update_interval(x, dat[2*c+1].r, 2*c+1, val);
    update_interval(dat[2*c+2].l, y, 2*c+2, val);
  }

  T query(int x, int y, int c) {
    node &cur = dat[c];

    cur.val = op(cur.val, times(cur.r - cur.l + 1, cur.delayed));
    if (cur.l != cur.r) {
      dat[2*c+1].delayed = op(dat[2*c+1].delayed, cur.delayed);
      dat[2*c+2].delayed = op(dat[2*c+2].delayed, cur.delayed);
    }
    cur.delayed = init_val;

    if (x == cur.l && y == cur.r) {
      return cur.val;
    }

    if (x >= cur.l && y <= dat[2*c+1].r) {
      return query(x, y, 2*c+1);
    }

    if (y <= cur.r && x >= dat[2*c+2].l) {
      return query(x, y, 2*c+2);
    }

    return op(
        query(x, dat[2*c+1].r, 2*c+1),
        query(dat[2*c+2].l, y, 2*c+2));
  }
};

template<typename T, typename Func>
lazy_segtree<T, Func> build_lazy_segtree(int N, T init_val, Func op) {
  return lazy_segtree<T, Func>(N, init_val, op);
}


int main(int argc, char const* argv[])
{
  using namespace std;
  auto &&tree = build_lazy_segtree(100, string(""), [](string x, string y){ return x + y; });

  tree.update_interval(40, 50, string("abcd"));
  cout << tree.query(0, 99) << endl;
  
  return 0;
}