线段树：
线段树的定义
定义1 长度为1的线段称为元线段。
定义2 一棵树被成为线段树，当且仅当这棵树满足如下条件：
（1）
该树是一棵二叉树。
（2） 树中每一个结点都对应一条线段[a,b]。
（3）
树中结点是叶子结点当且仅当它所代表的线段是元线段。
（4） 树中非叶子结点都有左右两个子树，做子树树根对应线段[a , (a + b ) /
2]，右子树树根对应线段[( a + b ) / 2 , b]。
但是这种二叉树较为平衡，和静态二叉树一样，提前根据应用的部分建立好树形结构。针对性强，所以效率要高。一般来说，动态结构较为灵活，但是速度较慢；静态结构节省内存，速度较快。
线段树的性质与时空复杂度简介
下面介绍线段树的两个性质（证明略）。
性质1
长度范围为[1,L]的一棵线段树的深度不超过log(L-1) + 1。
性质2
线段树把区间上的任意一条长度为L的线段都分成不超过2logL条线段。
空间复杂度 存储一棵线段树的空间复杂度一般为O（L）。
时间复杂度
对于插入线段、删除线段，查找元素，查找区间最值等操作，复杂度一般都是O（log
L）。
线段树主要应用了平衡与分治的性质，所以基本时间复杂度都和log有关。我们在应用线段树解决问题的时候，应尽量在构造好线段树的时候，使每种操作在同一层面上操作的次数为O（1），这样能够维持整体的复杂度O（log
L）。
例题：
在自然数，且所有的数不大于30000的范围内讨论一个问题：现在已知n条线段，把端点依次输入告诉你，然后有m个询问，每个询问输入一个点，要求这个点在多少条线段上出现过；
最基本的解法当然就是读一个点，就把所有线段比一下，看看在不在线段中；
每次询问都要把n条线段查一次，那么m次询问，就要运算m*n次，复杂度就是O(m*n)
这道题m和n都是30000，那么计算量达到了10^9；而计算机1秒的计算量大约是10^8的数量级，所以这种方法无论怎么优化都是超时
-----
因为n条线段是固定的，所以某种程度上说每次都把n条线段查一遍有大量的重复和浪费；
线段树就是可以解决这类问题的数据结构
举例说明：已知线段[2,5]
[4,6]
[0,7]；求点2,4,7分别出现了多少次
在[0,7]区间上建立一棵满二叉树：（为了和已知线段区别，用【】表示线段树中的线段）
【0,7】
/
\
【0,3】
【4,7】
/ \
/
\
【0,1】
【2,3】
【4,5】
【6,7】
/
\ / \
/ \
/
\
【0,0】【1,1】【2,2】【3,3】【4,4】 【5,5】【6,6】【7,7】
三条已知线段插入过程：
[2,5]
--[2,5]与【0,7】比较，分成两部分：[2,3]插到左儿子【0,3】，[4,5]插到右儿子【4,7】
--[2,3]与【0,3】比较，插到右儿子【2,3】；[4,5]和【4,7】比较，插到左儿子【4,5】
--[2,3]与【2,3】匹配，【2,3】记录+1；[4,5]与【4,5】匹配，【4,5】记录+1
[4,6]
--[4,6]与【0,7】比较，插到右儿子【4,7】
--[4,6]与【4,7】比较，分成两部分，[4,5]插到左儿子【4,5】；[6,6]插到右儿子【6,7】
--[4,5]与【4,5】匹配，【4,5】记录+1；[6,6]与【6,7】比较，插到左儿子【6,6】
--[6,6]与【6,6】匹配，【6,6】记录+1
[0,7]
--[0,7]与【0,7】匹配，【0,7】记录+1
插入过程结束，线段树上的记录如下（红色数字为每条线段的记录n）：
【0,7】
1
/
\
【0,3】
【4,7】
0
0
/
\
/ \
【0,1】 【2,3】
【4,5】 【6,7】
0
1
2
0
/
\
/
\
/
\
/ \
【0,0】 【1,1】
【2,2】 【3,3】
【4,4】 【5,5】
6,6】 【7,7】
0
0
0 0
0
0
1
0
询问操作和插入操作类似，也是递归过程，略
2——依次把【0,7】 【0,3】
【2,3】【2,2】的记录n加起来，结果为2
4——依次把【0,7】 【4,7】
【4,5】【4,4】的记录n加起来，结果为3
7——依次把【0,7】 【4,7】
【6,7】【7,7】的记录n加起来，结果为1
不管是插入操作还是查询操作，每次操作的执行次数仅为树的深度——logN
建树有n次插入操作，n*logN，一次查询要logN，m次就是m*logN；总共复杂度O(n+m)*logN，这道题N不超过30000，logN约等于14，所以计算量在10^5～10^6之间，比普通方法快了1000倍；
hud1166:
/*------------------------------------------------ @file hdu1166 解题: 线段树模板 @author fripSide @date 2014/02/15 ------------------------------------------------*/ #include <cstdio> const int MAXN = 50009; struct line { int l; int r; int num; } Tree[MAXN << 2]; void modify(int t) { Tree[t].num = Tree[t << 1].num + Tree[t << 1 | 1].num; } void bulid(int l, int r, int t) { Tree[t].l = l; Tree[t].r = r; Tree[t].num = 0; if (l == r) { scanf("%d", &Tree[t].num); return; } int m = (l + r) >> 1; bulid(l, m, t << 1); bulid(m + 1, r, t << 1 | 1); modify(t); } void update(int v, int add, int t) { if (Tree[t].l == v && Tree[t].r == v) { Tree[t].num += add; return; } int m = (Tree[t].l + Tree[t].r) >> 1; if (v <= m) { update(v, add, t << 1); } else { update(v, add, t << 1 | 1); } modify(t); } int query(int l, int r, int t) { if (Tree[t].l == l && Tree[t].r == r) { return Tree[t].num; } int m = (Tree[t].l + Tree[t].r) >> 1; if (l > m) { //左子树 return query(l, r, t << 1 | 1); } else if (r <= m) { //右子树 return query(l, r, t << 1); } else { return query(l, m, t << 1) + query(m + 1, r, t << 1 | 1); } } int main() { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int t; while (scanf("%d", &t) != EOF && t != 0) { for (int cas = 1; cas <= t; ++cas) { printf("Case %d:\n", cas); int n; scanf("%d", &n); bulid(1, n, 1); char op[9]; while (scanf("%s", op) != EOF) { if (op[0] == ‘E‘) { break; } int a, b; scanf("%d%d", &a, &b); if (op[0] == ‘Q‘) { printf("%d\n", query(a, b, 1)); } else if (op[0] == ‘A‘) { update(a, b, 1); } else { update(a, -b, 1); } } } } return 0; }
hud1754
1 /*------------------------------------------------ 2 @file jd1456 3 解题: 4 线段树 5 1.建树 6 2.修改 7 3.查询 8 9 @author fripSide 10 @date 2014/02/11 11 ------------------------------------------------*/ 12 13 #include <cstdio> 14 #include <algorithm> 15 16 using namespace std; 17 18 const int MAXN = 200009; 19 20 struct line { 21 int l; 22 int r; 23 int cmax; 24 } Tree[MAXN * 4]; 25 26 void pushUp(int t) { 27 int x = t << 1; 28 Tree[t].cmax = max(Tree[x + 1].cmax, Tree[x + 2].cmax); 29 } 30 31 void buildTree(int l, int r, int t) { //[l, r] t表示结点编号 32 Tree[t].l = l; 33 Tree[t].r = r; 34 Tree[t].cmax = 0; 35 if (l == r) { //叶结点 36 scanf("%d", &Tree[t].cmax); 37 return; 38 } 39 int x = (l + r) >> 1; 40 buildTree(l, x, t << 1 | 1); 41 buildTree(x + 1, r, (t << 1) + 2); 42 pushUp(t); 43 } 44 45 void updateTree(int v, int cn, int t) { 46 if (Tree[t].l == v && Tree[t].r == v) { 47 Tree[t].cmax = cn; 48 return; 49 } 50 int m = (Tree[t].l + Tree[t].r) >> 1; 51 if (v <= m) { 52 updateTree(v, cn, t << 1 | 1); 53 } else { 54 updateTree(v, cn, (t << 1) + 2); 55 } 56 pushUp(t); 57 } 58 59 int queryTree(int l, int r, int t) { 60 if (Tree[t].l == l && Tree[t].r == r) { 61 return Tree[t].cmax; 62 } 63 int m = (Tree[t].l + Tree[t].r) >> 1; 64 if (l > m) { 65 return queryTree(l, r, (t << 1) + 2); 66 } else if (r <= m) { 67 return queryTree(l, r, t << 1 | 1); 68 } else { 69 int ret1 = queryTree(l, m, t << 1 | 1); 70 int ret2 = queryTree(m + 1, r, (t << 1) + 2); 71 return max(ret1, ret2); 72 } 73 } 74 75 int main() { 76 #ifndef ONLINE_JUDGE 77 freopen("in.txt", "r", stdin); 78 freopen("out.txt", "w", stdout); 79 #endif 80 int n, m; 81 while (scanf("%d%d", &n, &m) != EOF) { 82 buildTree(1, n, 0); 83 while (m--) { 84 char op[2]; 85 int a, b; 86 scanf("%s%d%d", op, &a, &b); 87 if (op[0] == ‘Q‘) { 88 printf("%d\n", queryTree(a, b, 0)); 89 } else { 90 updateTree(a, b, 0); 91 } 92 } 93 } 94 return 0; 95 }
原文：http://www.cnblogs.com/fripside/p/3551763.html
