H.Tree Recovery 時(shí)間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 131072K，其他語言262144K
64bit IO Format: %lld 鏈接：https://www.nowcoder.com/acm/contest/77/H
來源：牛客網(wǎng)

題目描述

You have?N?integers,?A₁,?A₂, ... ,?A_N. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

輸入描述:

輸出描述:

You need to answer all Q commands in order. One answer in a line. 示例1

輸入

10 5 1 2 3 4 5 6 7 8 9 10 Q 4 4 Q 1 10 Q 2 4 C 3 6 3 Q 2 4

輸出

4 55 9 15

?

這個(gè)題是線段樹區(qū)間查詢求和和區(qū)間更新。

?

代碼:

1 /*2 //H-線段樹-區(qū)間查詢求和和區(qū)間更新3 #include<iostream>4 #include<cstring>5 #include<cstdio>6 #include<cstdlib>7 #include<algorithm>8 using namespace std;9 typedef long long ll;10 #define ls l,m,rt<<111 #define rs m+1,r,rt<<1|112 #define root 1,n,113 const int maxn=1e5+10;14 ll Sum[maxn<<2],Add[maxn<<2];//Sum為求和，Add為懶惰標(biāo)記15 ll A[maxn],n;//存原數(shù)組數(shù)據(jù)下標(biāo)16 17 //PushUp函數(shù)更新節(jié)點(diǎn)信息，這里是求和18 void PushUp(int rt){19 Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1];20 }21 22 //下推標(biāo)記的函數(shù)23 void PushDown(int rt,int m){24 if(Add[rt]){//下推標(biāo)記25 Add[rt<<1]+=Add[rt];26 Add[rt<<1|1]+=Add[rt];27 Sum[rt<<1]+=Add[rt]*(m-(m>>1));28 Sum[rt<<1|1]+=Add[rt]*(m>>1);29 Add[rt]=0;//清除本節(jié)點(diǎn)標(biāo)記30 }31 }32 33 //建樹34 void Build(int l,int r,int rt){//rt表示當(dāng)前節(jié)點(diǎn)編號35 Add[rt]=0;36 if(l==r){37 Sum[rt]=A[l];return;38 }39 int m=(l+r)>>1;40 Build(ls);41 Build(rs);42 PushUp(rt);43 }44 45 //區(qū)間修改A[L,R]+=C46 void Update(int L,int R,int C,int l,int r,int rt){47 if(L<=l&&r<=R){48 Sum[rt]+=(ll)C*(r-l+1);49 Add[rt]+=C;50 return ;51 }52 PushDown(rt,r-l+1);//下推標(biāo)記53 int m=(l+r)>>1;54 if(L<=m)Update(L,R,C,ls);55 if(R>m)Update(L,R,C,rs);56 PushUp(rt);//更新本節(jié)點(diǎn)57 }58 59 //區(qū)間查詢A[L,R]的和60 int Query(int L,int R,int l,int r,int rt){61 if(L<=l&&r<=R){62 return Sum[rt];63 }64 PushDown(rt,r-l+1);//下推標(biāo)記，否則Sum可能不正確65 int m=(l+r)>>1;66 ll ANS=0;//累計(jì)答案67 if(L<=m)ANS+=Query(L,R,ls);68 if(R>m)ANS+=Query(L,R,rs);69 return ANS;70 }71 72 int main(){73 int n,m;74 scanf("%d%d",&n,&m);75 for(int i=1;i<=n;i++)76 scanf("%lld",&A[i]);77 Build(1,n,1);//建樹78 while(m--){79 char str[2];80 scanf("%s",str);81 if(str[0]=='Q'){82 int a,b;83 scanf("%d%d",&a,&b);84 ll ANS=Query(a,b,root);//區(qū)間查詢85 printf("%lld\n",ANS);86 }87 else{88 int a,b,C;89 scanf("%d%d%d",&a,&b,&C);90 Update(a,b,C,root);//區(qū)間修改91 }92 }93 return 0;94 }95 */96 /*97 樣例98 10 599 1 2 3 4 5 6 7 8 9 10 100 Q 4 4 101 Q 1 10 102 Q 2 4 103 C 3 6 3 104 Q 2 4 105 */

?

?

?

就這樣，還有二維線段樹，還沒寫，以后寫。

滾去看搜索了，簡直被虐爆了，難受。

?

轉(zhuǎn)載于:https://www.cnblogs.com/ZERO-/p/9711387.html

總結(jié)

以上是生活随笔為你收集整理的牛客网 2018年全国多校算法寒假训练营练习比赛（第五场） H.Tree Recovery-完全版线段树(区间更新、区间求和)...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。