http://dongxicheng.org/structure/segment-tree/
线段树，也叫区间树，是一个完全二叉树，它在各个节点保存一条线段（即“子数组”），因而常用于解决数列维护问题，它基本能保证每个操作的复杂度为O(lgN)。
线段树的基本操作主要包括构造线段树，区间查询和区间修改。
struct node { int ld,rd;//左右边界 node *lc,*rc;//左右孩子 int key;//信息域 如RMQ问题中，信息域中存储的是区间最大值 };
建树
//空树的建立，内含key值的初始化； //一般在主函数中首先调用 Node* root= buildtree(1,n);建立一棵新树 node *ctree(int a,int b) { node *p = new node; p->ld = a; p->rd = b; /*{ 初始化key值。 }*/ if(a==b) return p; p->lc = ctree(a,(a+b)/2); p->rc = ctree((a+b)/2+1,b); return p; }
一篇不错的文章 线段树的应用 离散化都有
http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464583.html