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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
| class Segment_Tree { #define lc u << 1 #define rc u << 1 | 1
private: struct Tree { int l, r, sum, tag; inline int len() { return r - l + 1; } inline void addtag(int k) { sum += len() * k, tag += k; } } tr[N << 2];
public: inline void pushup(int u) { tr[u].sum = tr[lc].sum + tr[rc].sum; }
void build(int u, int l, int r) { tr[u].l = l, tr[u].r = r; if (l == r) return tr[u].sum = a[l], void(0); int mid = l + r >> 1; build(lc, l, mid), build(rc, mid + 1, r); pushup(u); }
void pushdown(int u) { int &k = tr[u].tag; tr[lc].addtag(k), tr[rc].addtag(k); k = 0; }
void dot_modify(int u, int x, int k) { if (tr[u].l == tr[u].r) return tr[u].addtag(k), void(0); pushdown(u); int mid = tr[u].l + tr[u].r >> 1; dot_modify(u << 1 | (x > mid), x, k); pushup(u); }
void range_modify(int u, int l, int r, int k) { if (l <= tr[u].l && tr[u].r <= r) return tr[u].addtag(k), void(0); pushdown(u); int mid = tr[u].l + tr[u].r >> 1; if (l <= mid) range_modify(lc, l, r, k); if (r > mid) range_modify(rc, l, r, k); pushup(u); }
int query(int u, int l, int r) { if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum; pushdown(u); int mid = tr[u].l + tr[u].r >> 1, res = 0; if (l <= mid) res += query(lc, l, r); if (r > mid) res += query(rc, l, r); return res; } #undef lc #undef rc } SGT;
|