首页 > 代码库 > 【模板】 递归线段树 [2017年五月计划 清北学堂51精英班Day4]
【模板】 递归线段树 [2017年五月计划 清北学堂51精英班Day4]
P3372 【模板】线段树 1
题目描述
如题，已知一个数列，你需要进行下面两种操作：
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入输出格式
输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数，表示一个操作，具体如下：
操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k
操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和
输出格式：输出包含若干行整数，即为所有操作2的结果。
输入输出样例
输入样例#1：
5 51 5 4 2 32 2 41 2 3 22 3 41 1 5 12 1 4
输出样例#1：
11820
说明
时空限制：1000ms,128M
数据规模：
对于30%的数据：N<=8，M<=10
对于70%的数据：N<=1000，M<=10000
对于100%的数据：N<=100000，M<=100000
（数据已经过加强^_^，保证在int64/long long数据范围内）
样例说明：
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <algorithm> 6 #define max(a,b) ((a) > (b) ? (a) : (b)) 7 #define min(a,b) ((a) > (b) ? (b) : (a)) 8 #define lowbit(a) (a & (-(a))) 9 const int INF = 0x3f3f3f3f; 10 const int MAXN = 100000 + 10; 11 const int MAXM = 100000 + 10; 12 inline void read(long long &x) 13 { 14 x = 0;char ch = getchar();char c = ch; 15 while(ch > ‘9‘ || ch < ‘0‘)c = ch, ch = getchar(); 16 while(ch >= ‘0‘ && ch <= ‘9‘)x = x * 10 + ch - ‘0‘,ch = getchar(); 17 if(c == ‘-‘)x = -x; 18 } 19 20 long long stdata[MAXN << 2]; 21 long long stlazy[MAXN << 2]; 22 long long n,m; 23 24 25 void modify1(long long p, long long k, long long o = 1,long long l = 1,long long r = n) 26 { 27 if(l == r == p) 28 { 29 stdata[o] += k; 30 return; 31 } 32 long long mid = (l + r) >> 1; 33 if(p <= mid) modify1(p, k, o << 1, l, mid); 34 else modify1(p, k, o << 1 | 1, mid + 1, r); 35 stdata[o] = stdata[o << 1] + stdata[o << 1 | 1]; 36 return ; 37 } 38 39 40 void modify2(long long ll, long long rr, long long k, long long o = 1, long long l = 1, long long r = n) 41 { 42 if(l >= ll && r <= rr) 43 { 44 stlazy[o] += k; 45 stdata[o] += (r - l + 1) * k; 46 return; 47 } 48 if(ll <= l && rr <= r && rr >= l) 49 { 50 stdata[o] += k * (rr - l + 1); 51 } 52 else if(ll >= l && rr <= r) 53 { 54 stdata[o] += k * (rr - ll + 1); 55 } 56 else if(ll >= l && ll <= r && rr >= r) 57 { 58 stdata[o] += k * (r - ll + 1); 59 } 60 long long mid = (l + r) >> 1; 61 if(ll <= mid)modify2(ll, rr, k, o << 1, l, mid); 62 if(rr > mid) modify2(ll, rr, k, o << 1 | 1, mid + 1, r); 63 } 64 65 long long query(long long ll, long long rr, long long o = 1, long long l = 1, long long r = n) 66 { 67 long long mid = (l + r) >> 1; 68 if(ll <= l && rr >= r) 69 { 70 return stdata[o]; 71 } 72 if(stlazy[o]) 73 { 74 stlazy[o << 1] += stlazy[o]; 75 stlazy[o << 1 | 1] += stlazy[o]; 76 stdata[o << 1] += (mid - l + 1) * stlazy[o]; 77 stdata[o << 1 | 1] += (r - mid) * stlazy[o]; 78 stlazy[o] = 0; 79 } 80 long long ans = 0; 81 if(ll <= mid)ans += query(ll, rr, o << 1, l, mid); 82 if(rr > mid) ans += query(ll, rr, o << 1 | 1, mid + 1, r); 83 stdata[o] = stdata[o << 1] + stdata[o << 1 | 1]; 84 return ans; 85 } 86 87 long long num[MAXN]; 88 long long cnt; 89 void build(long long o = 1,long long l = 1,long long r = n) 90 { 91 if(l == r) 92 { 93 stdata[o] = num[++cnt]; 94 return; 95 } 96 long long mid = (l + r) >> 1; 97 build(o << 1, l, mid); 98 build(o << 1 | 1, mid + 1, r); 99 stdata[o] = stdata[o << 1] + stdata[o << 1 | 1];100 }101 102 long long tmp1,tmp2,tmp3,tmp4;103 104 int main()105 {106 read(n);read(m);107 for(long long i = 1;i <= n;i ++)108 {109 read(num[i]);110 }111 build();112 for(long long i = 1;i <= m;i ++)113 {114 read(tmp1);115 switch(tmp1)116 {117 case 1:118 {119 read(tmp1);read(tmp2);read(tmp3);120 modify2(tmp1, tmp2, tmp3);121 break;122 }123 case 2:124 {125 read(tmp1);read(tmp2);126 printf("%lld\n", query(tmp1, tmp2));127 }128 }129 }130 return 0;131 }
【模板】 递归线段树 [2017年五月计划 清北学堂51精英班Day4]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。