算法思想

先來(lái)看下線(xiàn)段樹(shù)長(zhǎng)什么樣：

有以下數(shù)組（為方便計(jì)算，數(shù)組下標(biāo)從1開(kāi)始）

我們把它轉(zhuǎn)換成線(xiàn)段樹(shù)，是長(zhǎng)這樣的：

1）葉子結(jié)點(diǎn)（綠色）存的都是原數(shù)組元素的值

2）每個(gè)父結(jié)點(diǎn)是它的兩個(gè)子節(jié)點(diǎn)的值的和

3）每個(gè)父結(jié)點(diǎn)記錄它表示區(qū)間的范圍，如上圖的“1-2”表示1到2的區(qū)間

下面我們來(lái)看看線(xiàn)段樹(shù)是如何降低操作復(fù)雜度的！

查詢(xún)操作

例如我們需要查詢(xún)2-5區(qū)間的和

使用遞歸的思想：

2~5的和

=2~3的和+4~5的和

=3+5+4~5的和

=3+5+11

=19

總之，就是沿著線(xiàn)段樹(shù)的劃分把區(qū)間分開(kāi)，再加到一塊就行啦！

修改操作

例如，我們要把結(jié)點(diǎn)2的值由3->5，線(xiàn)段樹(shù)需要沿著紅色部分一個(gè)一個(gè)改，直到根結(jié)點(diǎn)：

不管是修改操作還是查詢(xún)操作，時(shí)間復(fù)雜度都是O(logn)

下一步我們來(lái)看怎么實(shí)現(xiàn)線(xiàn)段樹(shù)！

算法實(shí)現(xiàn)

首先我們需要將原始數(shù)組建立成一顆線(xiàn)段樹(shù)，然后在樹(shù)的基礎(chǔ)上提供查詢(xún)和修改的操作。

建樹(shù)

觀(guān)察上圖，我們發(fā)現(xiàn)線(xiàn)段樹(shù)是一棵近似完全二叉樹(shù)，利用完全二叉樹(shù)的性質(zhì)，我們就可以直接用一個(gè)數(shù)組來(lái)存它。

就像上圖一樣把各個(gè)節(jié)點(diǎn)標(biāo)上號(hào)，如果根節(jié)點(diǎn)編號(hào)是n,那它的左子樹(shù)編號(hào)是2n,右子樹(shù)的編號(hào)是2n+1

所以說(shuō)，知道了根節(jié)點(diǎn)的編號(hào)，我們就可以快速有效的找到左右子樹(shù)的根節(jié)點(diǎn)

void build(int root,int start,int end){
    if(start == end){
        tree[root] = num[start];
        return;
    }
    int leftroot = root * 2;//左結(jié)點(diǎn)
    int rightroot = root * 2 + 1;//右結(jié)點(diǎn)
    int mid = (start+end)/2;
    build(leftroot,start,mid);//遞歸計(jì)算左結(jié)點(diǎn)
    build(rightroot,mid+1,end);//遞歸計(jì)算右結(jié)點(diǎn)
    tree[root] = tree[leftroot] + tree[rightroot];//根結(jié)點(diǎn)值=左根+右根
}

查詢(xún)

int query(int root,int start,int end,int l,int r){
    if(l<=start && r>= end){
        return tree[root];
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start+end)/2;
    int sum = 0;
    if(l<=mid){
        sum += query(leftroot,start,mid,l,r);
    }
    if(r>mid){
        sum += query(rightroot,mid+1,end,l,r);
    }
    return sum;
}

修改

/**
* 修改[l,r]區(qū)間里的數(shù)，都加上k值
* @param root
* @param start
* @param end
* @param l
* @param r
* @param k
*/
void update(int root,int start,int end,int l,int r,int k){
    if(start == end){
        tree[root] += k;
        return;
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start+end)/2;
    if(l<=mid){
        update(leftroot,start,mid,l,r,k);
    }
    if(r>mid){
        update(rightroot,mid+1,end,l,r,k);
    }
    tree[root] = tree[leftroot] + tree[rightroot];
}

?。。。嚎紤]下按區(qū)間修改元素值的復(fù)雜度？

注意事項(xiàng)：

1）我們?cè)趯?shí)現(xiàn)線(xiàn)段樹(shù)時(shí)，實(shí)際存儲(chǔ)肯定大于原始數(shù)組，我們一般讓tree數(shù)組的長(zhǎng)度為原始數(shù)據(jù)長(zhǎng)度的3-4倍。

2）本文只是為了讓大家學(xué)習(xí)線(xiàn)段樹(shù)的實(shí)現(xiàn)原理，實(shí)際中我們可以將原始數(shù)組的start，end使用結(jié)構(gòu)體存儲(chǔ)，這樣更簡(jiǎn)潔

總結(jié)

到此這篇關(guān)于線(xiàn)段樹(shù)詳解以及C++實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)線(xiàn)段樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！