线段树
题意:
分析:
以前没学线段树时,看一些题解总是会有这句话“这题可以用线段树做,当然不必这么麻烦。。。。。”
总会产生兴趣,线段树是什么呀。上了雨神的课终于是清楚了。
能够解决复杂问题的线段树也是起于简单的想法的呢。
不说了看着一题,很明显是区间求和问题。那么重点便为我们的lazy标记了!
我们lazy标记应该为什么呢?标记这个区间最左端的元素值!而这个区间一定要应该从头到尾都是等差的
即a1,a1+1,a1+2,a1+3......我们这样规定。
这样就可以了。。。。。。
#include<iostream> #include<algorithm> using namespace std; #define lson now<<1 #define rson now<<1|1 typedef long long ll; const int max_n = 1e5 + 100; int n, m; struct node { int l, r, lazy;ll w; }tree[max_n << 2]; void build(int l,int r,int now) { tree[now].l = l;tree[now].r = r;tree[now].lazy = 0; if (l == r) { cin >> tree[now].w; return; } int mid = (tree[now].l + tree[now].r) >> 1; build(l, mid, lson); build(mid + 1, r, rson); tree[now].w = tree[lson].w + tree[rson].w; } void pushdown(int now) { if (tree[now].lazy) { tree[lson].lazy = tree[now].lazy; tree[rson].lazy = tree[now].lazy + tree[lson].r - tree[lson].l + 1; tree[lson].w = (tree[lson].r - tree[lson].l + 1) * (2 * tree[lson].lazy + tree[lson].r - tree[lson].l) >> 1; tree[rson].w = (tree[rson].r - tree[rson].l + 1) * (2 * tree[rson].lazy + tree[rson].r - tree[rson].l) >> 1; tree[now].lazy = 0; } } void renew(int x,int y,int k,int now) { if (tree[now].l >= x && tree[now].r <= y) { tree[now].lazy = tree[now].l - x + k; tree[now].w = (tree[now].r - tree[now].l + 1) * (2 * tree[now].lazy + tree[now].r - tree[now].l) >> 1; return; } if (tree[now].lazy)pushdown(now); int mid = (tree[now].l + tree[now].r) >> 1; if (mid >= x)renew(x, y, k, lson); if (mid < y)renew(x, y, k, rson); tree[now].w = tree[lson].w + tree[rson].w; } ll quiry(int x, int y,int now) { if (tree[now].l >= x && tree[now].r <= y)return tree[now].w; if (tree[now].lazy)pushdown(now); int mid = (tree[now].l + tree[now].r) >> 1; ll ans = 0; if (mid >= x)ans += quiry(x, y, lson); if (mid < y)ans += quiry(x, y, rson); return ans; } int main() { ios::sync_with_stdio(0); cin >> n >> m;build(1, n, 1); while (m--) { int type;cin >> type; if (type == 1) { int l, r, k; cin >> l >> r >> k; renew(l, r, k, 1); } else { int l, r;cin >> l >> r; cout << quiry(l, r, 1) << endl; } } }