線段樹
要解決的問題
數組任意區間內的元素修改，增加，求和，時間複雜度都要達到O(logN)水平, 方法說明如下
L...R上都加V
void add(L, R, V, arr)
L...R上的值都更新成V
void update(L, R, V, arr)
L...R上求和並返回求和資訊
int query(L, R, arr)
預處理
線段樹要求數組長度必須是2^N次方，如果不滿足，則通過補0的方式來變成2^N次方。
將數組劃分成一個個的區間，區間大小分別為: 1，2，4，8.... 2^N。
例如：數組的長度為8，我們將數組下標從1開始編號到8，則每個下標構成的區間是一個滿二叉樹，如下圖
1~8
/ \
1~4 5~8
/ \ / \
1~2 3~4 5~6 7~8
/ \ / \ / \ / \
1 2 3 4 5 6 7 8
如果不滿足2的n次方，要變成滿二叉樹，需要通過補0的方式，比如數組只有6個元素，編號為1~6，那麼7位置和8位置補0。
如果N滿足2的某次方，則僅需要2N個區間就可以裝下所有區間，如果不滿足2的某次方，則僅需要4N個區間就可以裝下。
線段樹這裡的下標都用1開始，0位置棄而不用 就是為了在任意位置（假設位置為i）有：
左孩子對應的下標是2*i ，即：i<<1
右孩子對應的下標是2*i+1，即：(i<<1)|1
所以，假設原始數組長度為N，線段樹需要將這個數組做如下預處理：
第一步，準備一個N+1長度的數組arr，arr的0位置棄而不用，其他位置依次存原始數組的值。
第二步，準備四個數組，數組長度均為：4*(N+1)，每個數組的含義如下
sum數組用來模擬維護區間和
lazy數組為累加和懶惰標記
change數組為更新的值數組
update數組存放更新慵懶標記
線段樹初始化
線段樹在初始化階段，會把每個區間的和先計算出來，放入sum數組中，初始化程式碼如下
public void build(int l, int r, int rt) {
if (l == r) {
sum[rt] = arr[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushUp(rt);
}
private void pushUp(int rt) {
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
pushUp方法很容易理解，即：每個區間的和等於它左右兩個區間的和相加得到。前面提到，對於rt位置來說，左右孩子分別為rt << 1和rt << 1 | 1。所以sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];。
build方法用了遞歸，根據master公式可以計算其複雜度為O(logN)。
區間內每個數都加一個值
即線段樹的add方法，源碼如下
public void add(int L, int R, int C, int l, int r, int rt) {
// 任務如果把此時的範圍全包了！
if (L <= l && r <= R) {
sum[rt] += C * (r - l + 1);
lazy[rt] += C;
return;
}
int mid = (l + r) >> 1;
pushDown(rt, mid - l + 1, r - mid);
if (L <= mid) {
add(L, R, C, l, mid, rt << 1);
}
if (R > mid) {
add(L, R, C, mid + 1, r, rt << 1 | 1);
}
pushUp(rt);
}
註：L...R為任務區間，即需要在L...R這個區間內的值，都加上一個C值。
如果任務的範圍把此時數組某個劃分區間l...r包住了，則這個l...r這個區間範圍內的值都要加上C,
即程式碼中base case的第一個邏輯sum[rt] += C * (r - l + 1), 而lazy[rt] += C;表示加C這個任務hold在l...r區間內，不下發給子節點處理，這就是線段樹的懶更新機制。
如果任務的範圍無法把數組某個劃分區間l...r包住，則l...r這個區間就要下發給左右子樹進行處理。但是在下發之前，要進行pushDown操作，在pushDown操作中，add方法會觸發到的邏輯是：
private void pushDown(int rt, int ln, int rn) {
if (update[rt]) {
update[rt << 1] = true;
update[rt << 1 | 1] = true;
change[rt << 1] = change[rt];
change[rt << 1 | 1] = change[rt];
lazy[rt << 1] = 0;
lazy[rt << 1 | 1] = 0;
sum[rt << 1] = change[rt] * ln;
sum[rt << 1 | 1] = change[rt] * rn;
update[rt] = false;
}
if (lazy[rt] != 0) {
lazy[rt << 1] += lazy[rt];
sum[rt << 1] += lazy[rt] * ln;
lazy[rt << 1 | 1] += lazy[rt];
sum[rt << 1 | 1] += lazy[rt] * rn;
lazy[rt] = 0;
}
}
由於目前沒有涉及update操作，所以現在只看pushDown方法的如下分支
if (lazy[rt] != 0) {
lazy[rt << 1] += lazy[rt];
sum[rt << 1] += lazy[rt] * ln;
lazy[rt << 1 | 1] += lazy[rt];
sum[rt << 1 | 1] += lazy[rt] * rn;
lazy[rt] = 0;
}
這個操作表示，在l...r把任務下發到左右子樹之前，先把l...r之前hold住的更新,即lazy[rt]中存的值，同步下發到左右子樹進行更新，其中就包括兩步：
第一步，左右子樹都要加上之前父節點的lazy值，因為當時父節點在更新lazy的時候，是沒有下發到左右子樹的(懶更新)，此時要下發了，就必須把之前所有的lazy資訊更新到左右子樹，對應就是程式碼中的如下兩行
lazy[rt << 1] += lazy[rt];
lazy[rt << 1 | 1] += lazy[rt];
第二步，左右子樹的sum值，也會隨著父節點的lazy值更新過來而整體更新，對應程式碼中如下兩行
sum[rt << 1 | 1] += lazy[rt] * rn;
sum[rt << 1] += lazy[rt] * ln;
pushDown的這兩個步驟時間複雜度O(logN)。
此時，執行完pushDown操作後，就可以下發任務了，核心程式碼如下
if (L <= mid) {
add(L, R, C, l, mid, rt << 1);
}
if (R > mid) {
add(L, R, C, mid + 1, r, rt << 1 | 1);
}
pushUp(rt);
使用的類似二分的方式，主要判斷依據是任務區間到底在左右子樹的哪個子樹範圍內。最後，執行pushUp方法，即把累加資訊傳遞給父節點。
綜上，線段樹的add邏輯說明完畢。
區間內的值都更新為某個值
即線段樹的update方法，update方法需要change數組和update數組配合。
public void update(int L, int R, int C, int l, int r, int rt) {
if (L <= l && r <= R) {
update[rt] = true;
change[rt] = C;
sum[rt] = C * (r - l + 1);
lazy[rt] = 0;
return;
}
// 當前任務躲不掉，無法懶更新，要往下發
int mid = (l + r) >> 1;
pushDown(rt, mid - l + 1, r - mid);
if (L <= mid) {
update(L, R, C, l, mid, rt << 1);
}
if (R > mid) {
update(L, R, C, mid + 1, r, rt << 1 | 1);
}
pushUp(rt);
}
base case的邏輯和add方法類似，如果任務範圍包住了區間範圍，則在區間內直接做更新,update[rt] = true用於標識這個區間做了更新；change[rt] = C;用於記錄這個區間的值更新成了什麼；如果一個節點收到一個update方法，假設更新為C, 這個C存在change數組中，而且這個區間的所有lazy資訊失效，這個區間的sum值直接變成數據個數 * C，所以有如下邏輯。
sum[rt] = C * (r - l + 1);
lazy[rt] = 0;
如果任務包不住區間範圍，和add類似，也需要下發，下發過程可以查看pushDown邏輯的如下分支：
if (update[rt]) {
update[rt << 1] = true;
update[rt << 1 | 1] = true;
change[rt << 1] = change[rt];
change[rt << 1 | 1] = change[rt];
lazy[rt << 1] = 0;
lazy[rt << 1 | 1] = 0;
sum[rt << 1] = change[rt] * ln;
sum[rt << 1 | 1] = change[rt] * rn;
update[rt] = false;
}
下發過程中，左右子樹的更新標誌位都需要設置為true, 且左右子樹區間需要更新的值均為父區間需要更新的值，即
update[rt << 1] = true;
update[rt << 1 | 1] = true;
change[rt << 1] = change[rt];
change[rt << 1 | 1] = change[rt];
由於區間需要更新，所以lazy失效，sum可以直接計算出來（數組區間元素個數*更新值）
任務下發後，和add方法一樣，判斷更新的區間在哪個子樹範圍，遞歸調用update執行更新操作即可，最後更新完畢後，需要把更新後的左右子樹之和資訊傳給父節點的sum資訊中。
綜上，線段樹的update方法說明完畢。
返回區間之和
和add以及update方法類似，
public long query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R) {
return sum[rt];
}
int mid = (l + r) >> 1;
pushDown(rt, mid - l + 1, r - mid);
long ans = 0;
if (L <= mid) {
ans += query(L, R, l, mid, rt << 1);
}
if (R > mid) {
ans += query(L, R, mid + 1, r, rt << 1 | 1);
}
return ans;
}
求和之前，如果任務範圍沒包住區間範圍，要執行一次pushDown操作，才能把各個相關區間的資訊最後整合出來。
線段樹的適用場景
父節點如果可以通過左右簡單加工得到，就可以用線段樹
什麼時候不能用線段樹呢？
比如：要求某個區間出現次數最多的值（這個無法用線段樹，因為出現次數最多的值可以既不是左邊出現最多的值，也不是右邊出現最多的值）
線段樹源碼
相關題目
LeetCode_0307_RangeSumQuery
LeetCode_0303_RangeSumQueryImmutable
LeetCode_0699_FallingSquares
