今天继续来复习二叉树的变种——线段树，实现一些基本操作

线段树：

线段树是一种二叉搜索树，但它的每个节点储存了：值data，区间左端点，区间右端点，因此，一棵线段树代表的是一个线段。根节点的左右子树也是线段树，分别储存了线段的左半部分和线段的右半部分，直到叶节点左右端点相等。
我们有递归定义：
对于一棵线段树T（a，b），记区间长度为L：
当L>1:有左子树T(a,(a+b)/2)
右子树T((a+b)/2+1,b)
L=1:叶子节点
(我习惯把单个值写为叶子节点，方便修改和询问（估计不对- -之后来修改))

随便画个示意图：

讯享网

线段树构建（c++）：

线段树节点：
构造函数
储存的数据
线段的左右端点
左右子节点的指针
对于线段树操作（查询，插入，修改）的实现一般都是递归的思想，看看代码注释就懂了
代码实现：

#include<iostream> #include<string> using std::string; class SegmentTreeNode{ 
    public: SegmentTreeNode():min(0),max(0),lchild(NULL),rchild(NULL){ 
   } int min; int max; int data; SegmentTreeNode *lchild; SegmentTreeNode *rchild; }; //initiate SegmentTreeNode *CreateTree(int xmin,int xmax) { 
    //judge valid segment if(xmax-xmin<0) { 
    std::cout<<"wrong segment"<<std::endl; return NULL; } SegmentTreeNode *root=new SegmentTreeNode; root->lchild=NULL; root->rchild=NULL; root->data=0; root->min=xmin; root->max=xmax; //recursion if(xmax-xmin==0) { 
    return root; } else if(xmax-xmin>0) { 
    int xmid=(xmax+xmin)/2; //递归创建左右子树 root->lchild=CreateTree(xmin,xmid); root->rchild=CreateTree(xmid+1,xmax); } return root; } //find data int find(SegmentTreeNode* tree,int No) { 
    if(tree->min==No&&tree->max==No) { 
    return tree->data; } //设定中值，用移位运算应该还能加速 int mid=(tree->min+tree->max)/2; if(No<=mid) { 
    return find(tree->lchild,No); } else { 
    //递归查找 return find(tree->rchild,No); } } //update data（经常改动，可以设置为内联函数） int update(SegmentTreeNode* tree,int No,int value) { 
    if(tree->min==No&&tree->max==No) { 
    tree->data=value; return tree->data; } int mid=(tree->min+tree->max)/2; if(No<=mid)//在左边 { 
    //递归修改父母的值 tree->data = update(tree->lchild,No,value)+tree->rchild->data; return tree->data; } else { 
    //递归修改父母的值 tree->data =update(tree->rchild,No,value)+tree->lchild->data; return tree->data; } } //segment query(x<y!) int query(SegmentTreeNode *tree,int x,int y) { 
    if(tree->min==x&&tree->max==y) { 
    return tree->data; } int mid=(tree->min+tree->max)/2; if(y<=mid) { 
    return query(tree->lchild,x,y); } if(x>mid) { 
    return query(tree->rchild,x,y); } return query(tree->lchild,x,mid)+query(tree->rchild,mid+1,y); } //update a segment int updateSegment(SegmentTreeNode *tree,int x,int y,int value) { 
    if(tree->min==tree->max&&tree->min==x) { 
    tree->data+=value; return tree->data; } int mid=(tree->min+tree->max)/2; if(y<=mid) { 
    tree->data=updateSegment(tree->lchild,x,y,value)+tree->rchild->data; return tree->data; } if(x>mid) { 
    tree->data=updateSegment(tree->rchild,x,y,value)+tree->lchild->data; return tree->data; } tree->data=updateSegment(tree->lchild,x,mid,value)+updateSegment(tree->rchild,mid+1,y,value); return tree->data; } //遍历，用来测试是否创建出来了 void traversing(SegmentTreeNode *root) { 
    if(root!=NULL) { 
    std::cout<<root->min<<" "<<root->max<<std::endl; traversing(root->lchild); traversing(root->rchild); } }

线段树的查询修改非常高效，下回来贴点题目（咕