線段樹(shù)的概念

線段樹(shù)，英文名稱是Segment Tree，其本質(zhì)也是一個(gè)二叉搜索樹(shù)，區(qū)別在于線段樹(shù)的每一個(gè)節(jié)點(diǎn)記錄的都是一個(gè)區(qū)間，每個(gè)區(qū)間都被平均分為2個(gè)子區(qū)間，作為它的左右兒子。比如說(shuō)區(qū)間[1，10]，被分為區(qū)間[1，5]作為左兒子，區(qū)間[6，10]作為右兒子：

為什么要設(shè)計(jì)這樣奇怪的數(shù)據(jù)結(jié)構(gòu)呢？

線段樹(shù)主要適用于某些相對(duì)罕見(jiàn)的應(yīng)用場(chǎng)景：

比如給定了若干元素，要求統(tǒng)計(jì)出不同區(qū)間范圍內(nèi)，元素的個(gè)數(shù)。

現(xiàn)在我們已經(jīng)知道了什么是線段樹(shù)，那么看一個(gè)利用線段樹(shù)的例子。

線段樹(shù)的存儲(chǔ)與建造

這是一個(gè)序列：

現(xiàn)在我們要用它完成一個(gè)區(qū)間求和的任務(wù)。

區(qū)間求和就是指求序列中一段區(qū)間的所有元素之和。比如說(shuō)上面的序列，區(qū)間[1，5]的和為元素1+元素2+元素3+元素4+元素5，也就是14。再舉一個(gè)例子，區(qū)間[9，10]的和為9。

在學(xué)習(xí)線段樹(shù)的概念的時(shí)候，我們就知道線段樹(shù)的每個(gè)節(jié)點(diǎn)都存儲(chǔ)了一個(gè)區(qū)間。比如說(shuō)對(duì)于[1，10]這個(gè)節(jié)點(diǎn)，也就是這棵線段樹(shù)的根節(jié)點(diǎn)，那么它的值為1+5+1+3+4+2+0+9+0+9=34。看我們把這棵樹(shù)填完：

（當(dāng)一個(gè)區(qū)間的左右邊界已經(jīng)相等時(shí)，比如[1，1]，表示這個(gè)區(qū)間內(nèi)只有一個(gè)元素了，此時(shí)不能再分割，因此它就沒(méi)有左右兒子節(jié)點(diǎn)了）

現(xiàn)在就讓我們用代碼實(shí)現(xiàn)線段樹(shù)：

【代碼片段 1】 用一個(gè)類Node表示線段樹(shù)的節(jié)點(diǎn)：

class Node {
     int l; // l是區(qū)間左邊界
     int r; // r是區(qū)間右邊界
     int sum; // sum是區(qū)間元素和

     public Node (int l, int r, int sum){
         this.l = l;
         this.r = r;
         this.sum = sum;
     }
}

【代碼解析 1】 線段樹(shù)的任意節(jié)點(diǎn)都有3個(gè)屬性：

• 區(qū)間的左邊界l
• 區(qū)間的右邊界r
• 區(qū)間的元素和sum

比如說(shuō)在上面的線段樹(shù)中，區(qū)間[1,10]這個(gè)元素：

• 左邊界為1
• 右邊界為10
• 元素和為34

【代碼片段 2】 定義元素個(gè)數(shù)、原序列和線段樹(shù)

static int n = 10; // n是元素個(gè)數(shù)
static int[] array = {0, 1, 5, 1, 3, 4, 2, 0, 9, 0, 9}; 
// array是原序列(第一個(gè)0是占array[0]位的)
static Node[] tree = new Node[4*n];

static void initTree (){
    for(int i = 0; i < tree.length; i++){
        tree[i] = new Node(0, 0, 0, 0);
    }
}

【代碼解析 2】 首先我們?cè)谏衔囊呀?jīng)定義了元素個(gè)數(shù)和原序列。他們的值如下：

• 元素個(gè)數(shù)為10個(gè)
• 原序列為[0，1，5，1，3，4，2，0，9，0，9]

現(xiàn)在問(wèn)題在于，存儲(chǔ)線段樹(shù)的數(shù)組應(yīng)該開(kāi)多大的空間？根據(jù)證明發(fā)現(xiàn)，一個(gè)有n個(gè)元素的序列，所對(duì)應(yīng)的線段樹(shù)至少需要大小為4n的數(shù)組來(lái)存儲(chǔ)。這一類證明網(wǎng)上有很多，讀者可以自行查閱一下。

我們用inittree這個(gè)函數(shù)進(jìn)行線段樹(shù)初始化（tree數(shù)組初始值為null，不初始化會(huì)報(bào)錯(cuò)，我在這個(gè)地方卡了好久）

【代碼片段 3】 updateNode函數(shù)負(fù)責(zé)更新節(jié)點(diǎn)的值：

static void updateNode (int num) { // num是當(dāng)前節(jié)點(diǎn)序號(hào)
    tree[num].sum = tree[num * 2].sum + tree[num * 2 + 1].sum;
}

【代碼解析 3】 仔細(xì)觀察前面的線段樹(shù)可以發(fā)現(xiàn)，每一個(gè)節(jié)點(diǎn)的值都等于其左右兒子值的和。我們剛剛學(xué)會(huì)，一個(gè)編號(hào)為n的節(jié)點(diǎn)，其左右兒子分別為2n和2n+1。因此我們把num的值更新為2num+2num+1，也就是其左右兒子的和。

【代碼片段 4】 build函數(shù)建造線段樹(shù)：

static void build (int l, int r, int num) { // 建樹(shù)
    tree[num].l = l;
    tree[num].r = r;
    if (l == r) { // l = r說(shuō)明到達(dá)葉子節(jié)點(diǎn)
        tree[num].sum = array[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, num * 2); // 遞歸左兒子
    build(mid + 1, r, num * 2 + 1); // 遞歸右兒子
    updateNode(num);
}

【代碼解析 4】 函數(shù)從區(qū)間[l，r]開(kāi)始遞歸遍歷整棵線段樹(shù)，每一次都遞歸它的左右兒子，到葉子節(jié)點(diǎn)時(shí)結(jié)束。遞歸每一個(gè)兒子時(shí)，都對(duì)它進(jìn)行更新。這樣下來(lái)就完成了整棵樹(shù)的初始化。

線段樹(shù)的單點(diǎn)修改

現(xiàn)在假如我們需要把第6個(gè)元素從2修改為3：

那么就會(huì)有很多的區(qū)間相應(yīng)的改變。比如說(shuō)區(qū)間[5，7]，從4+2+0=6變成了4+3+0=7?，F(xiàn)在讓我們手動(dòng)模擬一下線段樹(shù)的單點(diǎn)修改過(guò)程。這里假設(shè)我們需要把元素6從2變成3：

首先，從根節(jié)點(diǎn)開(kāi)始遍歷，發(fā)現(xiàn)含有元素6的區(qū)間是根節(jié)點(diǎn)的右兒子，與左兒子沒(méi)有關(guān)系。因此將修改目標(biāo)鎖定到右兒子：

第二步，發(fā)現(xiàn)含有6的區(qū)間是左兒子，因此把目標(biāo)放到左兒子上：

第三步同理：

第四步同理：

此時(shí)發(fā)現(xiàn)這是一個(gè)葉子節(jié)點(diǎn)，因此對(duì)它進(jìn)行更新，從2變成3：

返回到上一層：

接下去同理：

然后我們跳過(guò)演示，讀者可以自己試試看用同樣的方法修改這棵樹(shù)。最后修改完應(yīng)該是這樣的：

根節(jié)點(diǎn)最后應(yīng)該從34變成35，我經(jīng)常會(huì)忘記修改它的值，大家千萬(wàn)不要忘記修改它。

演示完以后我們分析一下時(shí)間復(fù)雜度。如果我們使用線段樹(shù)修改元素，每次都是折半操作，相當(dāng)于二分查找的速度，時(shí)間復(fù)雜度僅僅是對(duì)數(shù)級(jí)別，也就是   。

【代碼片段 5】 modify函數(shù)實(shí)現(xiàn)單點(diǎn)修改：

static void modify (int i, int value, int num) { // 把元素i修改為值value
    if (tree[num].l == tree[num].r) { // 到達(dá)葉子節(jié)點(diǎn)
        tree[num].sum = value;
        return;
    }
    int mid = (tree[num].l + tree[num].r) / 2;
    if (i <= mid) {
        modify(i, value, num * 2); // 遞歸左兒子
    }
    else {
        modify(i, value, num * 2 + 1); // 遞歸右兒子
    }
    updateNode(num);
}

【代碼解析 5】 這一段代碼也不是很難。每一次我們都從根開(kāi)始遞歸遍歷。我們先判斷要更改的元素屬于當(dāng)前節(jié)點(diǎn)的左兒子還是右兒子，并且遞歸到該節(jié)點(diǎn)。遞歸結(jié)束后更新當(dāng)前節(jié)點(diǎn)的值。假如遍歷到葉子節(jié)點(diǎn)，說(shuō)明我們已經(jīng)遍歷到了想要修改的元素，那么我們直接把該節(jié)點(diǎn)的值修改為value就可以了。

到這里我們已經(jīng)學(xué)會(huì)了單點(diǎn)修改的方法了。接下來(lái)讓我們更進(jìn)一步，學(xué)習(xí)區(qū)間修改。

線段樹(shù)的區(qū)間修改

首先讓我們明確一下區(qū)間修改的概念：

單點(diǎn)修改，大致是以下兩個(gè)步驟：

1. 找到需要修改的點(diǎn)
2. 修改這個(gè)點(diǎn)

而區(qū)間修改是這樣兩個(gè)步驟：

1. 找到需要修改的區(qū)間
2. 修改這段區(qū)間內(nèi)的所有點(diǎn)

好的，概念我們明白了，現(xiàn)在要知道如何實(shí)現(xiàn)這個(gè)功能。首先我們看一看區(qū)間修改可能的情況：

1. 需要修改的區(qū)間包含在兒子之內(nèi)：

   為大家畫(huà)個(gè)圖：

   我們看到需修改區(qū)間[6，8]包含在未修改區(qū)間的右兒子里。這種情況很簡(jiǎn)單，我們直接遞歸到右兒子即可。

2. 需要修改的區(qū)間被拆開(kāi)：

   還是畫(huà)一個(gè)圖：

   這時(shí)4屬于左兒子，但是5和6屬于右兒子。這怎么辦呢？最直接的方法是把這個(gè)區(qū)間拆成兩半，屬于左兒子的放一邊，屬于右兒子的放一邊，像這樣：

兩種情況分類討論后，我們就要考慮如何修改區(qū)間了。

最簡(jiǎn)單的方法就是把這些區(qū)間挨個(gè)兒修改。但是大家可以試試看，這種方法比暴力還要慢好幾倍。因此我們需要使用懶惰標(biāo)記。

現(xiàn)在假如我們需要把區(qū)間[5，7]每個(gè)元素增加2：

首先，5屬于根節(jié)點(diǎn)的左兒子，而6和7屬于根節(jié)點(diǎn)的右兒子，因此兩邊都要進(jìn)行修改。我們可以先修改左兒子：

5屬于當(dāng)前節(jié)點(diǎn)的右兒子，因此我們鎖定右兒子：

5屬于當(dāng)前節(jié)點(diǎn)的右兒子，那么我們修改右兒子。我們發(fā)現(xiàn)右兒子就是5。當(dāng)前只有一個(gè)元素，因此我們把當(dāng)前的值+2，并為其打上一個(gè)懶惰標(biāo)記，懶惰標(biāo)記的值也是2：

之后向上回溯，每一個(gè)節(jié)點(diǎn)都進(jìn)行更新，也就是說(shuō)每一個(gè)節(jié)點(diǎn)都更新為其左兒子+右兒子，最后更新完是這樣的：

到目前為止，懶惰標(biāo)記還沒(méi)有發(fā)揮作用，但是我們可以看一看6和7這段區(qū)間的修改。首先因?yàn)?和7在根節(jié)點(diǎn)的右兒子，因此我們先遍歷右兒子：

接著因?yàn)?和7在當(dāng)前節(jié)點(diǎn)的左兒子，因此我們遍歷左兒子：

之后我們發(fā)現(xiàn)6和7就是當(dāng)前節(jié)點(diǎn)的左兒子，因此我們直接遍歷到左兒子，修改其值并打上懶惰標(biāo)記。需要指出的是，因?yàn)?~7有2個(gè)元素，因此增加的值要乘2，也就是從+2變?yōu)?4，但懶惰標(biāo)記的值不用乘2：

此時(shí)讓我們思考一個(gè)問(wèn)題：

我們還需要遍歷修改[6，6]和[7，7]嗎？

這時(shí)就不用了，因?yàn)槲覀円呀?jīng)打上了懶惰標(biāo)記，懶惰標(biāo)記的初衷就是延遲修改，因此我們當(dāng)然不需要再修改這兩個(gè)節(jié)點(diǎn)了?，F(xiàn)在讓我們一鼓作氣，回溯到根節(jié)點(diǎn)，完成所有更新：

現(xiàn)在我們一起用代碼實(shí)現(xiàn)：

【代碼片段 6】 為Node類添加懶惰標(biāo)記：

class Node {
     int l; // l是區(qū)間左邊界
     int r; // r是區(qū)間右邊界
     int sum; // sum是區(qū)間元素和
     int lazy; // lazy是懶惰標(biāo)記

     public Node (int l, int r, int sum, int lazy){
         this.l = l;
         this.r = r;
         this.sum = sum;
         this.lazy = lazy;
     }
}

【代碼解析 6】 新增了lazy變量作為懶惰標(biāo)記。

【代碼片段 7】 modifySegment函數(shù)實(shí)現(xiàn)區(qū)間修改的代碼：

static void modifySegment(int l, int r, int value, int num) { // [l,r]每一項(xiàng)都增加value
    if (tree[num].l == l && tree[num].r == r) { // 找到當(dāng)前區(qū)間
        tree[num].sum += ( r - l + 1 ) * value; // r-l+1是區(qū)間元素個(gè)數(shù)
        tree[num].lazy += value;
        return;
    }
    int mid = (tree[num].l + tree[num].r) / 2;
    if (r <= mid) { // 在左區(qū)間
        modifySegment(l, r, value, num * 2);
    }
    else if (l > mid) { // 在右區(qū)間
        modifySegment(l, r, value, num * 2 + 1);
    }
    else { // 分成2塊
        modifySegment(l, mid, value, num * 2);
        modifySegment(mid + 1, r, value, num * 2 + 1);
    }
    updateNode(num);
}

【代碼解析 7】  首先，按照開(kāi)始講的3種情況，進(jìn)行分類討論（情況分別是：完全在左區(qū)間，完全在右區(qū)間，分成了2塊），并且向下遞歸。

線段樹(shù)的區(qū)間查詢

區(qū)間查詢，顧名思義就是查詢一段區(qū)間內(nèi)的元素和。那么如何實(shí)現(xiàn)呢？

不急，現(xiàn)在我們來(lái)看這樣一種情況：

[1，2]有一個(gè)懶惰標(biāo)記2?，F(xiàn)在假如我要求[1，1]的值怎么辦？

涼拌

為什么我這么說(shuō)？因?yàn)閇1，2]這個(gè)節(jié)點(diǎn)有一個(gè)懶惰標(biāo)記，但是[1，1]卻沒(méi)有被更新，這是一個(gè)問(wèn)題。

此時(shí)我們就要實(shí)現(xiàn)一個(gè)函數(shù)，用于把懶惰標(biāo)記下傳給兒子們，稱為pushdown函數(shù)。下面直接給代碼，解析部分請(qǐng)看代碼解析吧：

【代碼片段 8】 使用pushdown函數(shù)下傳懶惰標(biāo)記：

static void pushdown (int num) {
    if(tree[num].l == tree[num].r) { // 葉節(jié)點(diǎn)不用下傳標(biāo)記
        tree[num].lazy = 0; // 清空當(dāng)前標(biāo)記
        return;
    }
    tree[num * 2].lazy += tree[num].lazy; // 下傳左兒子的懶惰標(biāo)記
    tree[num * 2 + 1].lazy += tree[num].lazy; // 下傳右兒子的懶惰標(biāo)記
    tree[num * 2].sum += (tree[num * 2].r - tree[num * 2].l + 1) * tree[num].lazy; // 更新左兒子的值
    tree[num * 2 + 1].sum += (tree[num * 2 + 1].r - tree[num * 2 + 1].l + 1) * tree[num].lazy; // 更新右兒子的值
    tree[num].lazy=0; // 清空當(dāng)前節(jié)點(diǎn)的懶惰標(biāo)記
}

【代碼解析 8】 下傳懶惰標(biāo)記步驟有3步：

1. 將懶惰標(biāo)記傳遞給兒子
2. 更新兒子的值
3. 清空當(dāng)前節(jié)點(diǎn)的懶惰標(biāo)記

需要注意的是，葉子節(jié)點(diǎn)不用下傳標(biāo)記。

現(xiàn)在我們完成了pushdown函數(shù)的編寫(xiě)，可以開(kāi)始學(xué)習(xí)區(qū)間查詢了。剛才我們完成了區(qū)間修改，并且將原序列修改為了[1，5，1，3，6，4，2，9，0，9]。現(xiàn)在我們接著實(shí)現(xiàn)區(qū)間查詢問(wèn)題。假如我們要查詢區(qū)間[5，6]：

正如我們所見(jiàn)，答案為10?，F(xiàn)在告訴大家一個(gè)好消息，那就是區(qū)間查詢的大致步驟其實(shí)和區(qū)間修改沒(méi)有什么出入。讓我們來(lái)實(shí)踐一下：

首先，5和6分別屬于根節(jié)點(diǎn)的左兒子和右兒子，那我們先遍歷左兒子：

接著繼續(xù)往下：

往下查找到[5，5]：

記錄好這邊答案為6。接著我們看根節(jié)點(diǎn)的右兒子，查找元素6：

向下搜索到[6，8]：

搜索到[6，7]：

此時(shí)我們需要下傳[6，7]的懶惰標(biāo)記，并且更新[6，6]的值，如下：

最后遍歷到[6，6]，值為4，與剛才得到的6相加，答案就是10：

那么我們上代碼：

【代碼片段 9】 query函數(shù)實(shí)現(xiàn)區(qū)間查詢：

static int query (int l, int r, int num) {
    if (tree[num].lazy != 0) { // 下傳懶惰標(biāo)記
        pushdown(num);
    }
    if (tree[num].l == l && tree[num].r == r) { // 找到當(dāng)前區(qū)間
        return tree[num].sum;
    }
    int mid = (tree[num].l + tree[num].r) / 2;
    if (r <= mid) { // 在左區(qū)間
        return query(l, r, num * 2);
    }
    if (l > mid) { // 在右區(qū)間
        return query(l, r, num * 2 + 1);
    }
    return query(l, mid, num * 2) + query(mid + 1, r, num * 2 + 1); // 分成2塊
}

【代碼解析 9】 步驟與區(qū)間修改完全相同，記得要pushdown一下就行。

static int n = 10; // n是元素個(gè)數(shù)
static int[] array = {0, 1, 5, 1, 3, 4, 2, 0, 9, 0, 9};
// array是原序列(第一個(gè)0是占array[0]位的)
static Node[] tree = new Node[4*n]; // tree是線段樹(shù)

public static void main(String[] args) {
    initTree();
    build(1, 10, 1); // 利用build函數(shù)建樹(shù)
    System.out.println("操作1：[2，5]的區(qū)間和是：" + query(2, 5, 1));
    // 利用query函數(shù)搜索區(qū)間和
    modify(5, 9, 1); // 利用modify函數(shù)實(shí)現(xiàn)單點(diǎn)修改（元素5從4改為9）
    System.out.println("操作2：元素5從4改為9，此時(shí)[2，5]的區(qū)間和是：" + query(2, 5, 1));
    modifySegment(3, 4, 3, 1);
    // 利用modifySegment函數(shù)將[3，4]每個(gè)元素增加3
    System.out.println("操作3：區(qū)間[3，4]每個(gè)元素+3，此時(shí)[2，5]的區(qū)間和是：" + query(2, 5, 1));
}

static void initTree (){
    for(int i = 0; i < tree.length; i++){
        tree[i] = new Node(0, 0, 0, 0);
    }
}

static void updateNode (int num) { // num是當(dāng)前節(jié)點(diǎn)序號(hào)
    tree[num].sum = tree[num * 2].sum + tree[num * 2 + 1].sum;
}

static void build (int l, int r, int num) { // 建樹(shù)
    tree[num].l = l;
    tree[num].r = r;
    if (l == r) { // l = r說(shuō)明到達(dá)葉子節(jié)點(diǎn)
        tree[num].sum = array[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, num * 2); // 遞歸左兒子
    build(mid + 1, r, num * 2 + 1); // 遞歸右兒子
    updateNode(num);
}

static void modify (int i, int value, int num) { // 把元素i修改為值value
    if (tree[num].l == tree[num].r) { // 到達(dá)葉子節(jié)點(diǎn)
        tree[num].sum = value;
        return;
    }
    int mid = (tree[num].l + tree[num].r) / 2;
    if (i <= mid) {
        modify(i, value, num * 2); // 遞歸左兒子
    }
    else {
        modify(i, value, num * 2 + 1); // 遞歸右兒子
    }
    updateNode(num);
}

static void modifySegment(int l, int r, int value, int num) { // [l,r]每一項(xiàng)都增加value
    if (tree[num].l == l && tree[num].r == r) { // 找到當(dāng)前區(qū)間
        tree[num].sum += ( r - l + 1 ) * value; // r-l+1是區(qū)間元素個(gè)數(shù)
        tree[num].lazy += value;
        return;
    }
    int mid = (tree[num].l + tree[num].r) / 2;
    if (r <= mid) { // 在左區(qū)間
        modifySegment(l, r, value, num * 2);
    }
    else if (l > mid) { // 在右區(qū)間
        modifySegment(l, r, value, num * 2 + 1);
    }
    else { // 分成2塊
        modifySegment(l, mid, value, num * 2);
        modifySegment(mid + 1, r, value, num * 2 + 1);
    }
    updateNode(num);
}

static void pushDown(int num) {
    if(tree[num].l == tree[num].r) { // 葉節(jié)點(diǎn)不用下傳標(biāo)記
        tree[num].lazy = 0; // 清空當(dāng)前標(biāo)記
        return;
    }
    tree[num * 2].lazy += tree[num].lazy; // 下傳左兒子的懶惰標(biāo)記
    tree[num * 2 + 1].lazy += tree[num].lazy; // 下傳右兒子的懶惰標(biāo)記
    tree[num * 2].sum += (tree[num * 2].r - tree[num * 2].l + 1) * tree[num].lazy; // 更新左兒子的值
    tree[num * 2 + 1].sum += (tree[num * 2 + 1].r - tree[num * 2 + 1].l + 1) * tree[num].lazy; // 更新右兒子的值
    tree[num].lazy=0; // 清空當(dāng)前節(jié)點(diǎn)的懶惰標(biāo)記
}

static int query (int l, int r, int num) {
    if (tree[num].lazy != 0) { // 下傳懶惰標(biāo)記
        pushDown(num);
    }
    if (tree[num].l == l && tree[num].r == r) { // 找到當(dāng)前區(qū)間
        return tree[num].sum;
    }
    int mid = (tree[num].l + tree[num].r) / 2;
    if (r <= mid) { // 在左區(qū)間
        return query(l, r, num * 2);
    }
    if (l > mid) { // 在右區(qū)間
        return query(l, r, num * 2 + 1);
    }
    return query(l, mid, num * 2) + query(mid + 1, r, num * 2 + 1); // 分成2塊
}

static class Node {
    int l; // l是區(qū)間左邊界
    int r; // r是區(qū)間右邊界
    int sum; // sum是區(qū)間元素和
    int lazy; // lazy是懶惰標(biāo)記

    public Node (int l, int r, int sum, int lazy){
        this.l = l;
        this.r = r;
        this.sum = sum;
        this.lazy = lazy;
    }
}

          

           

            

             

              

               

                

                 
                
                

                 給個(gè)[在看]，是對(duì)小灰最大的支持！