超級常用的小工具:)

簡介

線段樹是一種二叉搜索樹，與區(qū)間樹相似，它將一個區(qū)間劃分成一些單元區(qū)間，每個單元區(qū)間對應(yīng)線段樹中的一個葉結(jié)點，能快速查詢特定區(qū)間的和；主要操作分為建樹、修改、查詢。

建樹

一種類似DFS的方法構(gòu)建一棵二叉樹，從上到下、從左到右標記樹的節(jié)點,一號節(jié)點是[1,n]，二號節(jié)點就是[1,n/2],三號節(jié)點為[n/2+1,n];以此類推

某渣渣自畫:)

核心代碼：
void build_tree(int now, int l, int r){
    if(l==r){
        scanf("%d", &tp[now]);
        return;
    }
    int mid=(l+r)/2;
    build_tree(now*2, l, mid);
    build_tree(now*2+1, mid+1, r);
    tp[now]=tp[now*2]+tp[now*2+1];
}

修改

重新更新了一次節(jié)點，每個涉及到的節(jié)點都會被更新，從而形成新的線段樹(二叉樹);相當于構(gòu)建樹的簡化版?(其實都一樣)

核心代碼：
void update(int now, int l, int r){
    if(l==r && l==pos){
        tp[now]=val;
        return;
    }
    int mid=(l+r)/2;
    if(mid>=pos)
        update(now*2, l, mid);
    else
        update(now*2+1, mid+1, r);
    tp[now]=tp[now*2]+tp[now*2+1];
}

查詢

我們已經(jīng)得到了一個區(qū)間簡化的樹，那么問題來了，總不可能不求區(qū)間值吧？
我們的樹構(gòu)建的時候用的是二分的思想，很多時候需要幾個節(jié)點相加，還記得節(jié)點代表的是哪段區(qū)間嗎？
不記得也沒關(guān)系，你只需要知道當你現(xiàn)在的區(qū)間的l大于等于所求的L，左邊包含一部分數(shù)據(jù)是你需要的；當你現(xiàn)在的區(qū)間的r小于所求的R的時候，右邊數(shù)據(jù)必定是有你需要的；（>=?）

核心代碼：
int query(int now, int l, int r){
    if(L<=l && r<=R)
        return tp[now];
    int sum=0;
    int mid=(l+r)/2;
    if(L<=mid)
        sum+=query(now*2, l, mid);
    if(R>mid)
        sum+=query(now*2+1, mid+1, r);
    return sum;
}

有沒有感覺上述代碼非常像？
是的，他就是非常像，理解第一個之后剩下的勢如破竹，
相應(yīng)的變形代碼也很容易構(gòu)建(比如[l,r]加減x)，
線段樹的應(yīng)用絕對不止這一點，有心的大佬多刷刷題就會理解里面的奧妙了