本文主要是介绍【线段树】-POJ-3468-区间增减区间求和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
依然是模板，原版来自hh大神
题目链接：http://poj.org/problem?id=3468
lazy的思想还是蛮有用的吧。。不只是线段树
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
typedef long long ll;
using namespace std;#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int maxn = 100050;ll lazy[maxn<<2];
ll sum[maxn<<2];
void PushUp(int rt) {sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void PushDown(ll rt,ll m) {if (lazy[rt]) {lazy[rt<<1] += lazy[rt];lazy[rt<<1|1] += lazy[rt];sum[rt<<1] += (m - (m >> 1)) * lazy[rt];sum[rt<<1|1] += (m >> 1) * lazy[rt];lazy[rt] = 0;}
}
void build(ll l,ll r,ll rt) {lazy[rt] = 0;if (l == r) {scanf("%I64d",&sum[rt]);return ;}int m = (l + r) >> 1;build(lson);build(rson);PushUp(rt);
}
void update(ll L,ll R,ll c,ll l,ll r,ll rt) {if (L <= l && r <= R) {lazy[rt] += c;sum[rt] += c * (r - l + 1);return ;}PushDown(rt , r - l + 1);int m = (l + r) >> 1;if (L <= m) update(L , R , c , lson);if (R > m) update(L , R , c , rson);PushUp(rt);
}ll query(ll L,ll R,ll l,ll r,ll rt)
{if(L<=l && R>=r) return sum[rt];PushDown(rt, r-l+1);int m = (l+r) >>1;ll ret=0;if(L<=m) ret += query(L,R,lson);if(R>m) ret += query(L,R,rson);return ret;
}int main() {freopen("input.txt","r",stdin);int N,Q;memset(lazy,0,sizeof(lazy));memset(sum,0,sizeof(sum));scanf("%d%d",&N,&Q);build(1,N,1);//cout<<N<<" "<<Q<<endl;while(Q--){char op[2];ll a,b,c;scanf("%s",op);//cout<<op<<endl;if(op[0] == 'Q'){scanf("%I64d%I64d",&a,&b);//cout<<a<<" "<<b<<endl;printf("%I64d\n",query(a,b,1,N,1));}else{scanf("%I64d%I64d%I64d",&a,&b,&c);update(a,b,c,1,N,1);}}return 0;
}
这篇关于【线段树】-POJ-3468-区间增减区间求和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
