999精品,丝袜综合,大陆老熟妇性,中国老女人AV,亚洲精品国产第一区二区三区

(相關資料圖)

線段樹--解決區(qū)間問題的數(shù)據(jù)結構，相比于樹狀數(shù)組，更具有普適性；

完全二叉樹的性質：根節(jié)下標為1，，節(jié)點為 i 的節(jié)點，左子節(jié)點為2*i，右子節(jié)點為2*i+1；

代表nums中單個元素的節(jié)點tree[x]應當在樹的最底層，即葉子節(jié)點；更大的區(qū)間從葉子節(jié)點開始向上構成；

代表區(qū)間【L，R】的節(jié)點 tree【i】，左子節(jié)點tree【2*i】表示區(qū)間【L，（L+R）/2】的區(qū)間和；右子節(jié)點tree【2*i+1】表示區(qū)間 【（L+R）/2 +1， R】的區(qū)間和；

初始化tree數(shù)組的大小 總是 令 其 為 4*n；類似于歸并排序、快排的分治算法，將原問題不斷的劃分為左右子問題；

代碼摘自：線段樹從入門到急停 - 力扣（LeetCode）非常詳細；

核心：一個就是注意單點修改時，遞歸結束條件的判斷，是查詢單點的話，就是 左右邊界相等終止；查詢區(qū)間和的話， 判斷當前區(qū)間是否落在 所求范圍內，是的話就加上這個區(qū)間；

另一個就是拓展：區(qū)間和數(shù)組可以替換為區(qū)間最值問題；求區(qū)間最大值、區(qū)間最小值等；

再一個就是區(qū)間修改問題，有兩種，一種是增量式修改，因為注意到我們的區(qū)間和，若不關注每個具體的值，只是區(qū)間和的大小，我們無需每次都向下更新到葉子節(jié)點，否則會達到O(N)時間復雜度；因此 需要增加一個 數(shù)組，判斷當前增量是否已經(jīng)向下更新，我們稱之為懶惰標記；； 第二種就是 覆蓋式修改：將區(qū)間的值都修改為同一值，此時，我們不能依據(jù)增量式修改的方法，因為可能修改為0，而向下更新的標記 也是檢查是否為0，從而 會產生沖突，所以另起一個數(shù)組，判斷是否已經(jīng)向下覆蓋；；

代碼實現(xiàn)：（此處將 兩種修改方法寫在一起了，建議分開寫）

#include using namespace std;class Segement_tree{private:    vectornums;    vectortree;    vectorlazy;    vectoris_updated;    int n;    void pushUp(int i){        tree[i] = tree[2*i] + tree[2*i + 1];    }    void build(int left, int right, int i){        if(left == right){            tree[i] = nums[left];        }        int mid = (left + right) / 2;        build(left, mid, 2*i);        build(mid + 1, right, 2*i + 1);        pushUp(i);    }    /*單點修改*/    void add(int index, int x, int left, int right, int i){        if(left == right){            tree[i] += x;            return;        }        int mid = (left + right)/2;        if(index <= mid){            add(index,x,left,mid,2*i);        }else{            add(index,x,mid+1,right,2*i+1);        }        pushUp(i);    }    void update(int index,int x,int left, int right,int i){        if(left == right){            tree[i] = x;            return;        }        int mid = (left + right) /2;        if(index <= mid){            update(index,x,left,mid,2*i);        }else{            update(index,x,mid+1,right,2*i+1);        }        pushUp(i);    }    int query(int index,int left,int right, int i){        if(left == right) return tree[i];        int mid = (left + right) /2;        if(index <= mid){            return query(index,left,mid,2*i);        }else{            return query(index,mid+1,right,2*i+1);        }    }    /*區(qū)間求和*/    int sum(int left, int right, int s, int t, int i){        if(left <= s && t <= right) return tree[i];        int mid = (s + t) /2;        int res = 0;        if(left <= mid){            res += sum(left,right, s, mid, 2*i);        }        if(right > mid){            res += sum(left,right, mid+1, t, 2*i+1);        }        return res;    }    /*區(qū)間修改： 增量式 */    void add(int left, int right, int x,int s, int t, int i){        if(left <= s && t <= right){            tree[i] += (t-s+1)*x;            if(s != t) lazy[i] += x;            return;        }        int mid = (s + t)/2;        if(lazy[i] != 0) pushDown(s,mid,t,i);        if(left <= mid) add(left,right,x,s,mid,2*i);        if(right > mid) add(left,right,x,mid+1,t,2*i+1);        pushUp(i);    }    void pushDown(int s,int mid, int t,int i){        tree[2*i] += (mid-s+1)*lazy[i];        lazy[2*i] += lazy[i];        tree[2*i+1] += (t-mid)*lazy[i];        lazy[2*i+1] += lazy[i];        lazy[i] = 0;    }    /*區(qū)間修改： 覆蓋式 */    void update(int left, int right,int x,int s,int t,int i){        if(left <= s && t <= right){            tree[i] = (t-s+1)*x;            if(s != t){                lazy[i] = x;                is_updated[i] = true;//未推送            }            return;        }        int mid = (s+t)/2;        if(is_updated[i]) pushDown1(s,mid,t,i);        if(left <= mid) update(left,right,x,s,mid,2*i);        if(right > mid) update(left,right,x,mid+1,t,2*i+1);        pushUp(i);    }    void pushDown1(int s,int mid,int t,int i){        tree[2*i] = (mid - s + 1)* lazy[i];        lazy[2*i] = lazy[i];        is_updated[2*i] = true;        tree[2*i+1] = (t - mid) * lazy[i];        lazy[2*i+1] = lazy[i];        is_updated[2*i+1] = true;        is_updated[i] = false;        lazy[i] = 0;    }public:    Segement_tree(vector& nums){        this->n = nums.size();        this->nums = nums;        this->tree.resize(4*n, 0);        this->lazy.resize(4*n, 0);        this->is_updated.resize(4*n, 0);        build(0, n-1, 1);    }    /*單點修改*/    void add(int index, int x){        add(index,x,0,n-1,1);    }    void update(int index,int x){        update(index,x,0,n-1,1);    }    int query(int index){        return query(index, 0, n-1,1);    }    /*區(qū)間求和*/    int sum(int left,int right){        return sum(left,right,0, n-1,1);    }    /*區(qū)間修改 ： 增量式*/    void add(int left,int right,int x){        add(left,right,x,0,n-1,1);    }    /*區(qū)間修改： 覆蓋式 */    void update(int left,int right, int x){        update(left,right,x,0,n-1,1);    }};int main(){    system("pause");    return 0;}