线段树
区间加
- struct Segment_Tree {
- #define ls (p <<1)
- #define rs (p <<1 | 1)
- #define mid ((l + r)>> 1)
- ll ans[_ <<2], tag[_ <<2];
- inline void pushup(ll p) { ans[p] = ans[ls] + ans[rs]; }
- inline void pushdown(ll p, ll l, ll r) {
- ans[ls] += (mid - l + 1) * tag[p];
- tag[ls] += tag[p];
- ans[rs] += (r - mid) * tag[p];
- tag[rs] += tag[p];
- tag[p] = 0;
- }
- void build(ll p, ll l, ll r) {
- if(l == r) {
- ans[p] = a[l];
- return;
- }
- build(ls, l, mid);
- build(rs, mid + 1, r);
- pushup(p);
- }
- void update(ll p, ll l, ll r, ll ul, ll ur, ll k) {
- if(ul <= l && r <= ur) {
- ans[p] += (r - l + 1) * k;
- tag[p] += k;
- return;
- }
- if(tag[p]) pushdown(p, l, r);
- if(ul <= mid) update(ls, l, mid, ul, ur, k);
- if(ur> mid) update(rs, mid + 1, r, ul, ur, k);
- pushup(p);
- }
- ll query(ll p, ll l, ll r, ll ql, ll qr) {
- if(ql <= l && r <= qr) return ans[p];
- if(tag[p]) pushdown(p, l, r);
- ll res = 0;
- if(ql <= mid) res += query(ls, l, mid, ql, qr);
- if(qr> mid) res += query(rs, mid + 1, r, ql, qr);
- return res;
- }
- #undef ls
- #undef rs
- #undef mid
- }T;
[笔记] 线段树 | 树状数组
来源: http://www.bubuko.com/infodetail-2978432.html