线段树(单点修改)

struct Info {
  friend Info operator + (Info a, Info b) {
    Info res = a;

    return res;
  }
};

struct SegmentTree {
  vector<Info> info;
  int n;
  SegmentTree() : n(0) { }
  SegmentTree(int n_) {
    n = n_;
    info.assign(4 << __lg(n), Info());
  }
  void build(int p, int l, int r, vector<Info> &v) {
    if (l == r) {
      info[p] = v[l];
      return;
    }
    int mid = l + r >> 1;
    build(p << 1, l, mid, v);
    build(p << 1 | 1, mid + 1, r, v);
    push_up(p);
  }
  void push_up(int p) {
    info[p] = info[p << 1] + info[p << 1 | 1];
  }
  void modify(int p, int l, int r, int x, const Info &v) {
    if (l == r) {
      info[p] = v;
      return;
    }
    int mid = l + r >> 1;
    if (x <= mid) {
      modify(p << 1, l, mid, x, v);
    } else {
      modify(p << 1 | 1, mid + 1, r, x, v);
    }
    push_up(p);
  }
  void modify(int x, const Info &v) {
    modify(1, 1, n, x, v);
  }
  Info range_query(int p, int l, int r, int x, int y) {
    if (l > y || r < x) {
      return Info();
    }
    if (l >= x && r <= y) {
      return info[p];
    }
    int mid = l + r >> 1;
    Info res = range_query(p << 1, l, mid, x, y) + range_query(p << 1 | 1, mid + 1, r, x, y);
    return res;
  }
  Info range_query(int l, int r) {
    return range_query(1, 1, n, l, r);
  }
};