Mythology
线段树入门
好久没写过算法了，添一个吧，写一个线段树的入门知识，比较大众化。
上次在湖大，其中的一道题数据很强，我试了好多种优化都TLE，相信只能用线段树才能过。回来之后暗暗又学了一次线段树，想想好像是第三次学了，像网络流一样每学一次都有新的体会。
把问题简化一下：
在自然数，且所有的数不大于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】每个节点用结构体：
struct line{ int left,right;//左端点、右端点 int n;//记录这条线段出现了多少次，默认为0}a[16];
和堆类似，满二叉树的性质决定a[i]的左儿子是a[2*i]、右儿子是a[2*i+1];
然后对于已知的线段依次进行插入操作：
从树根开始调用递归函数insert
void insert(int s,int t,int step)//要插入的线段的左端点和右端点、以及当前线段树中的某条线段{ if (s==a[step].left && t==a[step].right) { a[step].n++;//插入的线段匹配则此条线段的记录+1 return;//插入结束返回 } if (a[step].left==a[step].right) return;//当前线段树的线段没有儿子，插入结束返回 int mid=(a[step].left+a[step].right)/2; if (mid>=t) insert(s,t,step*2);//如果中点在t的右边，则应该插入到左儿子 else if (mid
三条已知线段插入过程：
[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倍；
这道题是线段树最基本的操作，只用到了插入和查找；删除操作和插入类似，扩展功能的还有测度、连续段数等等，在N数据范围很大的时候，依然可以用离散化的方法建树。
湖大的那道题目绕了个小弯子，alpc12有详细的题目和解题报告，有兴趣的话可以看看
线段树的经典题目就是poj1177的picture
【实例模板】
POJ 1007 求逆序数：
线段树解法
#include#include #include #include using namespace std; struct node { int lt; int rt; int num; } a[105]; struct pp { char str[55]; int cost; } ans[110]; void build(int s, int t, int step) { a[step].lt = s; a[step].rt = t; a[step].num = 0; if(a[step].lt == a[step].rt) return; int mid = (s + t) / 2; build(s, mid, 2 * step); build(mid + 1, t, 2 * step + 1); } void insert(int s, int t, int step) { if(a[step].lt == a[step].rt) { a[step].num++; return; } int mid = (a[step].lt + a[step].rt) / 2; if(t <= mid) insert(s, t, 2 * step); else if(s > mid) insert(s, t, 2 * step + 1); else { insert(s, mid, 2 * step); insert(mid + 1, t, 2 * step + 1); } a[step].num = a[2*step].num + a[2*step+1].num; } int query(int s, int t, int step) { if(a[step].lt == s && a[step].rt == t) { return a[step].num; } //if(a[step].lt==a[step].rt)return a[step].num; int mid = (a[step].lt + a[step].rt) / 2; if(t <= mid) return query(s, t, 2 * step); else if(s > mid) return query(s, t, 2 * step + 1); else return query(s, mid, 2 * step) + query(mid + 1, t, 2 * step + 1); } bool cmp(pp a, pp b) { return a.cost < b.cost; } int main() { int n, m; while(scanf("%d%d", &n, &m) != EOF) { getchar(); int i, j; for(i = 1; i <= m; i++) { scanf("%s", &ans[i].str); build(1, 26, 1); //note int sum = 0; for(j = n - 1; j >= 0; j--) { int val = ans[i].str[j] - 'A' + 1; int res = 0; if(val > 1) res = query(1, val - 1, 1); //note if val==1 sum += res; insert(val, val, 1); } ans[i].cost = sum; } sort(ans + 1, ans + m + 1, cmp); for(i = 1; i <= m; i++) { printf("%s\n", ans[i].str); } } }