segment tree(线段树)

简介 

        线段树(segment tree)是一种存储区间的树形结构，方便查询哪一个区间包含了指定的点，原则上，它是一种固定结构，
一旦建成该树，它的结构不会改变。

对于n个区间的集合，建一棵线段树的时间复杂度和空间复杂度都是O(nlgn)。
2. 定义
一维线段树结构：假设有一个区间集合，每一个区间元素从左到右依次是：。步骤：step1: 将所有的区间元素根据起始点和结束点进行排序；step2: 建一个平衡的二叉搜索树T,height(T)=O(lgn);step3 : 把这些区间插入T中，每插入一个元素需要O(lgn)时间；其中，最左边的叶子节点对应最左边的区间，叶子节点v对应区间Int[v]。
3. 实现
下面是线段树应用的一个例子，segment的区间对应数组的下标表示，值对应区间范围内所有数的总和。
class NumArray {    public:    class segmentTreeNode{        public:        int start,end;        int sum;        segmentTreeNode* left,*right;        segmentTreeNode(int start,int end)        {            this->start=start;            this->end=end;            sum=0;            left=right=NULL;        }    };    segmentTreeNode* build(vector<int>& nums,int s,int e)    {        if(s>e) return NULL;        segmentTreeNode *root=new segmentTreeNode(s,e);        if(s==e) root->sum=nums[s];        else{            int mid=s+(e-s)/2;            root->left=build(nums,s,mid);            root->right=build(nums,mid+1,e);            root->sum=root->left->sum+root->right->sum;        }        return root;    }    void update(segmentTreeNode* root,int i,int val)    {        if(root->start==root->end) root->sum=val;        else        {            int mid=root->start+(root->end-root->start)/2;            if(i<=mid)            update(root->left,i,val);            else update(root->right,i,val);            root->sum=root->left->sum+root->right->sum;        }    }    int sumRange(segmentTreeNode*root,int s,int e)    {        if(root->start==s&&root->end==e)        return root->sum;        int mid=root->start+(root->end-root->start)/2;        if(e<=mid) return sumRange(root->left,s,e);        else if(mid<s) return sumRange(root->right,s,e);        else return sumRange(root->left,s,mid)+sumRange(root->right,mid+1,e);    }    NumArray(vector<int> nums) {        root=build(nums,0,nums.size()-1);    }        void update(int i, int val) {        update(root,i,val);    }        int sumRange(int i, int j) {        int a= sumRange(root,i,j);        cout<<a<<endl;        return a;    }    PRivate:    segmentTreeNode* root;};
转载出于：1.点击打开链接2.点击打开链接