//线段树的节点
//节点包括两部分信息，基本域，和信息域
//基本域：左右边界leftboundary,rightboundary. 左右孩子：liftchild,rightchild //信息域：value值，如RMQ问题中，信息域中存储的是区间最大值
struct Node {
int leftboundary,rightboundary;
Node *leftchild,*rightchild;
typedef value;
};
//空树的建立，内含value值的初始化；
//一般在主函数中首先调用 Node* root= buildtree(1,n);建立一棵新树
Node *buildtree(int begin,int end)
{
Node *p = new Node;//给P申请一块内存
p -> leftboundary = begin;
p -> rightboundary = end;
//{p - > value 初始化}
if(begin == end)
return p;//叶子节点
p -> leftchild = buildtree(begin,(begin + end));
p -> rightchild = buildtree((begin + end) / 2 + 1,end);
return p;
}
void insert(Node *T,int begin,int end,int value)
{
if(begin <= T -> leftboundary && end >= T -> rightboundary)
{
//{根据value处理T -> value; 然后 return ;}
}
if(begin <= (T -> leftboundary + T -> rightboundary))
insert(T -> leftchild,a,b,value);
if(end > (T -> leftboundary + T -> rightboundary))
insert(T -> rightchlid,a,b,value);
//{根据T -> leftchild和T -> rightchild的信息处理T -> value} (此处类似于归并排序中最后的合并操作) }
int search(Node *T,int begin,int end)
{
int ans;
if(begin <= T -> leftchild && end >= T -> rightchild)
// {根据T -> value处理res;return res;}
if(a <= (T -> leftchild + T -> rightchild) / 2)
//{根据search(T -> leftchild,a,b)处理res}
if(b > (T -> leftchild+T -> rightchild) / 2)
//{根据search(T -> rightchild,a,b)处理res}
return res;
}
什么是线段树：
线段树是一种用树状结构来存储一个连续区间的信息的数据结构
线段树的作用：
它主要用于处理一段连续区间的插入，查找，统计，查询等操作
复杂度：
设区间的长度是n,所有的操作的复杂度是logN级别的
线段树的性质：
1.线段树是平衡二叉树，最大深度为logN(N为线段树所标示的区间的长度)
2任意的线段树[a,b]在线段树的查询或查找过程中把这个线段最多分成log(b-a)份
以上两条性质保证了线段树除了建树外的操作都是Log（N）级别的复杂度