<1>线段树的另一个知识点,区间点的成段更新,此处需要学习一下一个新的知识点,延迟标记.
<2>延迟标记是用来优化线段树的更新和查找的时间复杂度的,总的来说,就是对于当前找到的
这一段区间进行标记,然后覆盖其子区间,这样就可以节省时间,不必要去更新到叶子节点去;
不过如果下次需要修改到其子区间的话,在把延迟标记传给子区间就行,这就是pushup和pushdown
的意义;
#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <set>#include <queue>#include <vector>#include <cstdlib>#include <algorithm>#define ls u << 1#define rs u << 1 | 1#define lson l, mid, u << 1#define rson mid + 1, r, u << 1 | 1using namespace std;typedef long long ll;const int M = 1e5 + 100;ll sum[M << 2],tmp[M << 2];void pushup(int u){sum[u] = sum[ls] + sum[rs];}void pushdown(int l,int r,int u){int mid = (l + r) >> 1;if(tmp[u]){tmp[ls] += tmp[u];tmp[rs] += tmp[u];sum[ls] += (mid – l + 1) * tmp[u];sum[rs] += (r – mid) * tmp[u];tmp[u] = 0; //注意消除延迟标记.}}void build(int l,int r,int u){ //建树if(l == r){scanf("%I64d",sum + u);}else {int mid = (l + r) >> 1;build(lson);build(rson);pushup(u);}}void update(int L,int R,int c,int l,int r,int u){int mid = (l + r) >> 1;if(L <= l && R >= r){tmp[u] += c;sum[u] += 1LL * (r – l + 1) * c;return;}pushdown(l,r,u);if(L <= mid) update(L,R,c,lson);if(R > mid) update(L,R,c,rson);pushup(u);}ll query(int L,int R,int l,int r,int u){int mid = (l + r) >> 1;if(L <= l && R >= r){return sum[u];}ll res = 0;pushdown(l,r,u);if(L <= mid) res += query(L,R,lson);if(R > mid) res += query(L,R,rson);return res;}int main(){//freopen("in","r",stdin);int n,m;char s[10];cin>>n>>m;memset(tmp,0,sizeof(tmp));build(1,n,1);while(m–){int x,y;scanf("%s %d %d",s,&x,&y);if(s[0] == 'C'){int c;scanf("%d",&c);update(x,y,c,1,n,1);}else {printf("%I64d\n",query(x,y,1,n,1));}}return 0;}
，人若软弱就是自己最大的敌人
