線段樹是一個復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，比較難理解，也比較難解釋清楚。在我將這個數(shù)據(jù)結(jié)構(gòu)反復(fù)學(xué)習(xí)了五遍的時候，我終于有了信心寫出這篇介紹線段樹的文章。希望大家能夠掌握這種數(shù)據(jù)結(jié)構(gòu)。
這篇文章比較長，建議大家耐心閱讀，好好消化吸收哦~~
前置內(nèi)容
學(xué)習(xí)線段樹前，你需要掌握二叉搜索樹，不太了解的小伙伴，可以看看小灰之前發(fā)布的紅黑樹漫畫，前半部分講解了二叉搜索樹：
我只補充一個內(nèi)容，就是關(guān)于二叉搜索樹如何編號。
二叉搜索樹的根節(jié)點編號為1，對于每個節(jié)點，假如其編號為N，它的左兒子編號為2N，右兒子編號為2N+1。因此，整個二叉搜索樹的編號如下：
上圖當(dāng)中，結(jié)點上方的數(shù)字是結(jié)點的編號，后續(xù)為了簡單，把編號寫在結(jié)點內(nèi)不。
有讀者可能要問了，為什么3的兒子是6和7，而不是4和5呢？這是因為雖然節(jié)點4和節(jié)點5不存在，但是仍然應(yīng)該為他們保留4和5這2個編號，你可以把這棵樹看成這樣：
線段樹的概念
線段樹，英文名稱是Segment Tree，其本質(zhì)也是一個二叉搜索樹，區(qū)別在于線段樹的每一個節(jié)點記錄的都是一個區(qū)間，每個區(qū)間都被平均分為2個子區(qū)間，作為它的左右兒子。比如說區(qū)間[1，10]，被分為區(qū)間[1，5]作為左兒子，區(qū)間[6，10]作為右兒子：
為什么要設(shè)計這樣奇怪的數(shù)據(jù)結(jié)構(gòu)呢？
線段樹主要適用于某些相對罕見的應(yīng)用場景：
比如給定了若干元素，要求統(tǒng)計出不同區(qū)間范圍內(nèi)，元素的個數(shù)。
現(xiàn)在我們已經(jīng)知道了什么是線段樹，那么看一個利用線段樹的例子。
線段樹的存儲與建造
這是一個序列：
現(xiàn)在我們要用它完成一個區(qū)間求和的任務(wù)。
區(qū)間求和就是指求序列中一段區(qū)間的所有元素之和。比如說上面的序列，區(qū)間[1，5]的和為元素1+元素2+元素3+元素4+元素5，也就是14。再舉一個例子，區(qū)間[9，10]的和為9。
在學(xué)習(xí)線段樹的概念的時候，我們就知道線段樹的每個節(jié)點都存儲了一個區(qū)間。比如說對于[1，10]這個節(jié)點，也就是這棵線段樹的根節(jié)點，那么它的值為1+5+1+3+4+2+0+9+0+9=34?？次覀儼堰@棵樹填完：
（當(dāng)一個區(qū)間的左右邊界已經(jīng)相等時，比如[1，1]，表示這個區(qū)間內(nèi)只有一個元素了，此時不能再分割，因此它就沒有左右兒子節(jié)點了）
現(xiàn)在就讓我們用代碼實現(xiàn)線段樹：
【代碼片段 1】 用一個類Node表示線段樹的節(jié)點：
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】 線段樹的任意節(jié)點都有3個屬性：
- 區(qū)間的左邊界l
- 區(qū)間的右邊界r
- 區(qū)間的元素和sum
比如說在上面的線段樹中，區(qū)間[1,10]這個元素：
- 左邊界為1
- 右邊界為10
- 元素和為34
【代碼片段 2】 定義元素個數(shù)、原序列和線段樹
static int n = 10; // n是元素個數(shù)
static int[] array = {0, 1, 5, 1, 3, 4, 2, 0, 9, 0, 9};
// array是原序列(第一個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】 首先我們在上文已經(jīng)定義了元素個數(shù)和原序列。他們的值如下：
- 元素個數(shù)為10個
- 原序列為[0，1，5，1，3，4，2，0，9，0，9]
現(xiàn)在問題在于，存儲線段樹的數(shù)組應(yīng)該開多大的空間？根據(jù)證明發(fā)現(xiàn)，一個有n個元素的序列，所對應(yīng)的線段樹至少需要大小為4n的數(shù)組來存儲。這一類證明網(wǎng)上有很多，讀者可以自行查閱一下。
我們用inittree這個函數(shù)進行線段樹初始化（tree數(shù)組初始值為null，不初始化會報錯，我在這個地方卡了好久）
【代碼片段 3】 updateNode函數(shù)負責(zé)更新節(jié)點的值：
static void updateNode (int num) { // num是當(dāng)前節(jié)點序號
tree[num].sum = tree[num * 2].sum + tree[num * 2 + 1].sum;
}
【代碼解析 3】 仔細觀察前面的線段樹可以發(fā)現(xiàn)，每一個節(jié)點的值都等于其左右兒子值的和。我們剛剛學(xué)會，一個編號為n的節(jié)點，其左右兒子分別為2n和2n+1。因此我們把num的值更新為2num+2num+1，也就是其左右兒子的和。
【代碼片段 4】 build函數(shù)建造線段樹：
static void build (int l, int r, int num) { // 建樹
tree[num].l = l;
tree[num].r = r;
if (l == r) { // l = r說明到達葉子節(jié)點
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]開始遞歸遍歷整棵線段樹，每一次都遞歸它的左右兒子，到葉子節(jié)點時結(jié)束。遞歸每一個兒子時，都對它進行更新。這樣下來就完成了整棵樹的初始化。
線段樹的單點修改
現(xiàn)在假如我們需要把第6個元素從2修改為3：
那么就會有很多的區(qū)間相應(yīng)的改變。比如說區(qū)間[5，7]，從4+2+0=6變成了4+3+0=7。現(xiàn)在讓我們手動模擬一下線段樹的單點修改過程。這里假設(shè)我們需要把元素6從2變成3：
首先，從根節(jié)點開始遍歷，發(fā)現(xiàn)含有元素6的區(qū)間是根節(jié)點的右兒子，與左兒子沒有關(guān)系。因此將修改目標(biāo)鎖定到右兒子：
第二步，發(fā)現(xiàn)含有6的區(qū)間是左兒子，因此把目標(biāo)放到左兒子上：
第三步同理：
第四步同理：
此時發(fā)現(xiàn)這是一個葉子節(jié)點，因此對它進行更新，從2變成3：
返回到上一層：
接下去同理：
然后我們跳過演示，讀者可以自己試試看用同樣的方法修改這棵樹。最后修改完應(yīng)該是這樣的：
根節(jié)點最后應(yīng)該從34變成35，我經(jīng)常會忘記修改它的值，大家千萬不要忘記修改它。
演示完以后我們分析一下時間復(fù)雜度。如果我們使用線段樹修改元素，每次都是折半操作，相當(dāng)于二分查找的速度，時間復(fù)雜度僅僅是對數(shù)級別，也就是 。
【代碼片段 5】 modify函數(shù)實現(xiàn)單點修改：
static void modify (int i, int value, int num) { // 把元素i修改為值value
if (tree[num].l == tree[num].r) { // 到達葉子節(jié)點
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】 這一段代碼也不是很難。每一次我們都從根開始遞歸遍歷。我們先判斷要更改的元素屬于當(dāng)前節(jié)點的左兒子還是右兒子，并且遞歸到該節(jié)點。遞歸結(jié)束后更新當(dāng)前節(jié)點的值。假如遍歷到葉子節(jié)點，說明我們已經(jīng)遍歷到了想要修改的元素，那么我們直接把該節(jié)點的值修改為value就可以了。
到這里我們已經(jīng)學(xué)會了單點修改的方法了。接下來讓我們更進一步，學(xué)習(xí)區(qū)間修改。
線段樹的區(qū)間修改
首先讓我們明確一下區(qū)間修改的概念：
單點修改，大致是以下兩個步驟：
- 找到需要修改的點
- 修改這個點
而區(qū)間修改是這樣兩個步驟：
- 找到需要修改的區(qū)間
- 修改這段區(qū)間內(nèi)的所有點
好的，概念我們明白了，現(xiàn)在要知道如何實現(xiàn)這個功能。首先我們看一看區(qū)間修改可能的情況：
- 需要修改的區(qū)間包含在兒子之內(nèi)：為大家畫個圖：我們看到需修改區(qū)間[6，8]包含在未修改區(qū)間的右兒子里。這種情況很簡單，我們直接遞歸到右兒子即可。
- 需要修改的區(qū)間被拆開：還是畫一個圖：這時4屬于左兒子，但是5和6屬于右兒子。這怎么辦呢？最直接的方法是把這個區(qū)間拆成兩半，屬于左兒子的放一邊，屬于右兒子的放一邊，像這樣：
兩種情況分類討論后，我們就要考慮如何修改區(qū)間了。
最簡單的方法就是把這些區(qū)間挨個兒修改。但是大家可以試試看，這種方法比暴力還要慢好幾倍。因此我們需要使用懶惰標(biāo)記。
現(xiàn)在假如我們需要把區(qū)間[5，7]每個元素增加2：
首先，5屬于根節(jié)點的左兒子，而6和7屬于根節(jié)點的右兒子，因此兩邊都要進行修改。我們可以先修改左兒子：
5屬于當(dāng)前節(jié)點的右兒子，因此我們鎖定右兒子：
5屬于當(dāng)前節(jié)點的右兒子，那么我們修改右兒子。我們發(fā)現(xiàn)右兒子就是5。當(dāng)前只有一個元素，因此我們把當(dāng)前的值+2，并為其打上一個懶惰標(biāo)記，懶惰標(biāo)記的值也是2：
之后向上回溯，每一個節(jié)點都進行更新，也就是說每一個節(jié)點都更新為其左兒子+右兒子，最后更新完是這樣的：
到目前為止，懶惰標(biāo)記還沒有發(fā)揮作用，但是我們可以看一看6和7這段區(qū)間的修改。首先因為6和7在根節(jié)點的右兒子，因此我們先遍歷右兒子：
接著因為6和7在當(dāng)前節(jié)點的左兒子，因此我們遍歷左兒子：
之后我們發(fā)現(xiàn)6和7就是當(dāng)前節(jié)點的左兒子，因此我們直接遍歷到左兒子，修改其值并打上懶惰標(biāo)記。需要指出的是，因為6~7有2個元素，因此增加的值要乘2，也就是從+2變?yōu)?4，但懶惰標(biāo)記的值不用乘2：
此時讓我們思考一個問題：
我們還需要遍歷修改[6，6]和[7，7]嗎？
這時就不用了，因為我們已經(jīng)打上了懶惰標(biāo)記，懶惰標(biāo)記的初衷就是延遲修改，因此我們當(dāng)然不需要再修改這兩個節(jié)點了?，F(xiàn)在讓我們一鼓作氣，回溯到根節(jié)點，完成所有更新：
現(xiàn)在我們一起用代碼實現(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ù)實現(xiàn)區(qū)間修改的代碼：
static void modifySegment(int l, int r, int value, int num) { // [l,r]每一項都增加value
if (tree[num].l == l && tree[num].r == r) { // 找到當(dāng)前區(qū)間
tree[num].sum += ( r - l + 1 ) * value; // r-l+1是區(qū)間元素個數(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】 首先，按照開始講的3種情況，進行分類討論（情況分別是：完全在左區(qū)間，完全在右區(qū)間，分成了2塊），并且向下遞歸。
線段樹的區(qū)間查詢
區(qū)間查詢，顧名思義就是查詢一段區(qū)間內(nèi)的元素和。那么如何實現(xiàn)呢？
不急，現(xiàn)在我們來看這樣一種情況：
[1，2]有一個懶惰標(biāo)記2?，F(xiàn)在假如我要求[1，1]的值怎么辦？
涼拌
為什么我這么說？因為[1，2]這個節(jié)點有一個懶惰標(biāo)記，但是[1，1]卻沒有被更新，這是一個問題。
此時我們就要實現(xiàn)一個函數(shù)，用于把懶惰標(biāo)記下傳給兒子們，稱為pushdown函數(shù)。下面直接給代碼，解析部分請看代碼解析吧：
【代碼片段 8】 使用pushdown函數(shù)下傳懶惰標(biāo)記：
static void pushdown (int num) {
if(tree[num].l == tree[num].r) { // 葉節(jié)點不用下傳標(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é)點的懶惰標(biāo)記
}
【代碼解析 8】 下傳懶惰標(biāo)記步驟有3步：
- 將懶惰標(biāo)記傳遞給兒子
- 更新兒子的值
- 清空當(dāng)前節(jié)點的懶惰標(biāo)記
需要注意的是，葉子節(jié)點不用下傳標(biāo)記。
現(xiàn)在我們完成了pushdown函數(shù)的編寫，可以開始學(xué)習(xí)區(qū)間查詢了。剛才我們完成了區(qū)間修改，并且將原序列修改為了[1，5，1，3，6，4，2，9，0，9]?，F(xiàn)在我們接著實現(xiàn)區(qū)間查詢問題。假如我們要查詢區(qū)間[5，6]：
正如我們所見，答案為10。現(xiàn)在告訴大家一個好消息，那就是區(qū)間查詢的大致步驟其實和區(qū)間修改沒有什么出入。讓我們來實踐一下：
首先，5和6分別屬于根節(jié)點的左兒子和右兒子，那我們先遍歷左兒子：
接著繼續(xù)往下：
往下查找到[5，5]：
記錄好這邊答案為6。接著我們看根節(jié)點的右兒子，查找元素6：
向下搜索到[6，8]：
搜索到[6，7]：
此時我們需要下傳[6，7]的懶惰標(biāo)記，并且更新[6，6]的值，如下：
最后遍歷到[6，6]，值為4，與剛才得到的6相加，答案就是10：
那么我們上代碼：
【代碼片段 9】 query函數(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一下就行。
思考與探究
下面讓我們進行一些對于線段樹的思考與探究：
【思考 1】 線段樹都應(yīng)用于什么環(huán)境？除了區(qū)間和外，能否解決更多問題？比起別的樹有什么優(yōu)勢？
【答案 1】 線段樹一般多用于區(qū)間問題。在本文中我們解決的是區(qū)間和，但是也能解決更多的問題，比如區(qū)間平方和等等。線段樹只能解決符合下面條件的問題：
當(dāng)區(qū)間[l，r]可以由[l，mid(l，r)]和[mid(l，r) + 1，r]得到答案
我們舉幾個滿足條件的例子：
- 區(qū)間[5，8]的區(qū)間和，可以由[5，6]的區(qū)間和加上[7，8]的區(qū)間和得到。
- 區(qū)間[5，8]的最小值，等于區(qū)間[5，6]的最小值與[7，8]的最小值的最小值。
但是還有一些不滿足條件：
- 區(qū)間[5，8]的最長上升子序列。
另外就是線段樹比起別的樹的特點。線段樹屬于二叉搜索樹，像我們熟悉的紅黑樹、AVL樹其實也都屬于二叉搜索樹。只不過不同的二叉搜索樹用處不相同。線段樹比起別的樹，它的最大特點就是用作存儲區(qū)間的特性。
【思考 2】 線段樹和前綴和算法有什么優(yōu)劣區(qū)別嗎？
【答案 2】 寫到這里并不清楚各位是否明白前綴和算法。這里給大家簡單介紹一下：
對于任何一個序列，都能制作一個相對應(yīng)的前綴和數(shù)組。對于一個序列來講，假如我們用pre表示前綴和數(shù)組，那么pre[i]就表示區(qū)間[1，i]的區(qū)間和，比如pre[3]為array[1]+array[2]+array[3]，也就是7。
現(xiàn)在我們可用pre[i]表示區(qū)間[1，i]，那么假如有一個任意區(qū)間[l，r]，我們應(yīng)該怎么表示它的區(qū)間和呢？仔細思考一下不難發(fā)現(xiàn)，區(qū)間[l，r]的區(qū)間和其實就是區(qū)間[1，r]減去區(qū)間[1，l - 1]，剩下的也就是區(qū)間[l，r]了。因此我們可用pre[r]-pre[l-1]表示。
舉個例子，區(qū)間[3，5]的和為1+3+4=8，相當(dāng)于區(qū)間[1，5]減去區(qū)間[1，(3 - 1)]，也就是14-6=8。
我們發(fā)現(xiàn)，使用前綴和只要做一個減法就能得到區(qū)間和，而線段樹還要遍歷好多次，那是不是說，前綴和甚至要快于線段樹呢？我們可以來對比一下線段樹和前綴和的時間復(fù)雜度：
算法名稱初始化修改查詢前綴和O(n)O(n)O(1)線段樹O(log n)O(log n)O(log n)
我們發(fā)現(xiàn)，線段樹比起前綴和有更加穩(wěn)定的特點。它的每一項都是對數(shù)級別。而前綴和雖然查詢非?？?，但是修改速度就相對慢很多。因此我們認為，假如不需要進行元素的修改操作，那么我們一般選擇前綴和。如果需要進行元素修改操作，那么線段樹更為合適。
線段樹的完整代碼
最后，附上線段樹的完整代碼實現(xiàn)：
static int n = 10; // n是元素個數(shù)
static int[] array = {0, 1, 5, 1, 3, 4, 2, 0, 9, 0, 9};
// array是原序列(第一個0是占array[0]位的)
static Node[] tree = new Node[4*n]; // tree是線段樹
public static void main(String[] args) {
initTree();
build(1, 10, 1); // 利用build函數(shù)建樹
System.out.println("操作1：[2，5]的區(qū)間和是：" + query(2, 5, 1));
// 利用query函數(shù)搜索區(qū)間和
modify(5, 9, 1); // 利用modify函數(shù)實現(xiàn)單點修改（元素5從4改為9）
System.out.println("操作2：元素5從4改為9，此時[2，5]的區(qū)間和是：" + query(2, 5, 1));
modifySegment(3, 4, 3, 1);
// 利用modifySegment函數(shù)將[3，4]每個元素增加3
System.out.println("操作3：區(qū)間[3，4]每個元素+3，此時[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é)點序號
tree[num].sum = tree[num * 2].sum + tree[num * 2 + 1].sum;
}
static void build (int l, int r, int num) { // 建樹
tree[num].l = l;
tree[num].r = r;
if (l == r) { // l = r說明到達葉子節(jié)點
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) { // 到達葉子節(jié)點
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]每一項都增加value
if (tree[num].l == l && tree[num].r == r) { // 找到當(dāng)前區(qū)間
tree[num].sum += ( r - l + 1 ) * value; // r-l+1是區(qū)間元素個數(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é)點不用下傳標(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é)點的懶惰標(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;
}
}
