簡介 

        線段樹(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.點擊打開鏈接