首页 > 代码库 > 线段树---分析 && 模板总结
线段树---分析 && 模板总结
线段树：（转）
数据结构专题---线段树：http://blog.csdn.net/metalseed/article/details/8039326
线段树总结：http://blog.csdn.net/shiqi_614/article/details/8228102
概述：
线段树，类似区间树，是一个完全二叉树，它在各个节点保存一条线段（数组中的一段子数组），主要用于高效解决连续区间的动态查询问题，由于二叉结构的特性，它基本能保持每个操作的复杂度为O(lgN)!
性质：父亲的区间是[a,b],(c=(a+b)/2)左儿子的区间是[a,c]，右儿子的区间是[c+1,b]，线段树需要的空间为数组大小的四倍
Hdu 1066 敌兵布阵
·经典线段树应用：
Code：
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 #define lson l , m , rt << 1 6 #define rson m + 1 , r , rt << 1 | 1 7 #define root 1 , n , 1 8 #define LL long long 9 #define maxn 50000*510 11 LL ad[maxn<<2];12 LL su[maxn<<2];13 void PushUp(int rt) {14 su[rt] = su[rt<<1] + su[rt<<1|1];15 }16 void PushDown(int rt,int m) {17 if (ad[rt]) {18 ad[rt<<1] += ad[rt];19 ad[rt<<1|1] += ad[rt];20 su[rt<<1] += ad[rt] * (m - (m >> 1));21 su[rt<<1|1] += ad[rt] * (m >> 1);22 ad[rt] = 0;23 }24 }25 void build(int l,int r,int rt) {26 ad[rt] = 0;27 if (l == r) {28 scanf("%lld",&su[rt]);29 return ;30 }31 int m = (l + r) >> 1;32 build(lson);33 build(rson);34 PushUp(rt);35 }36 void update(int L,int R,int c,int l,int r,int rt) {37 if (L <= l && r <= R) {38 ad[rt] += c;39 su[rt] += (LL)c * (r - l + 1);40 return ;41 }42 PushDown(rt , r - l + 1);43 int m = (l + r) >> 1;44 if (L <= m) update(L , R , c , lson);45 if (m < R) update(L , R , c , rson);46 PushUp(rt);47 }48 LL query(int L,int R,int l,int r,int rt) {49 if (L <= l && r <= R) {50 return su[rt];51 }52 PushDown(rt , r - l + 1);53 int m = (l + r) >> 1;54 LL ret = 0;55 if (L <= m) ret += query(L , R , lson);56 if (m < R) ret += query(L , R , rson);57 return ret;58 }59 int main() {60 int n,number=1;61 int T;62 scanf("%d",&T);63 while(T--){64 printf("Case %d:\n",number++);65 scanf("%d",&n);66 build(root);67 char op[20];68 int a , b ;69 while (scanf("%s",op) && op[0]!=‘E‘) {70 if (op[0] == ‘Q‘) {71 scanf("%d%d",&a,&b);72 printf("%lld\n",query(a , b ,root));73 } else {74 scanf("%d%d",&a,&b);75 if(op[0]==‘A‘)76 update(a , a , b , root);77 else78 update(a , a , -b , root);79 80 }81 }82 }83 return 0;84 }
线段树---分析 && 模板总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。