1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <string.h>
class SegTree {
public:
  int left_, right_;
  int val_;
  SegTree *lch_, *rch_;
  bool add_flag_, change_flag_;
  int add_val_, change_val_;
  
  SegTree(int left, int right, int val,
          SegTree* lch = NULL, SegTree* rch = NULL) {
    left_ = left; right_ = right; val_ = val;
    lch_ = lch; rch_ = rch;
    add_flag_ = change_flag_ = false;
    add_val_ = change_val_ = 0;
  }
  static SegTree* build(int from, int to) {
    if (from == to) {
      int v; scanf("%d\n", &v);
      return new SegTree(from, to, v);
    }
    int mid = (from + to) / 2;
    SegTree* lch = build(from, mid);
    SegTree* rch = build(mid + 1, to);
    return new SegTree(from, to, lch->val_ + rch->val_, lch, rch);
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX