關(guān)于我的 Leetcode 題目解答，代碼前往 Github：https://github.com/chenxiangcyr/leetcode-answers
問題的引出
我們有時會遇到這樣的問題: 給你一些數(shù)耳鸯，組成一個序列竞川，如[1 4 2 3],有兩種操做:
- 操作一:給序列的第
i個數(shù)加上X(X可以為負(fù)數(shù)) - 操作二:詢問序列中最大的數(shù)是什么? 格式
query(start, end)，表示區(qū)間[start, end]內(nèi)酒唉，最大值是多少矩桂？
我們很容易得到一個樸素的算法: 將這些數(shù)存入一個數(shù)組, 由于要詢問最大值, 我們只需要遍歷這個區(qū)間[start, end]即可，找出最大值痪伦。
對于改變一個數(shù), 我們就在這個數(shù)上加上X侄榴，比如A[i] = A[i] + X雹锣。
這個算法的缺點是什么呢？Query詢問最大值復(fù)雜度O(N), 修改復(fù)雜度為O(1)癞蚕，在有Q個query的情況下這樣總的復(fù)雜度為O(QN), 那么對于查詢來說這樣的復(fù)雜度是不可以接受的蕊爵。
Segment Tree 線段樹
一顆線段樹的構(gòu)造就是根據(jù)區(qū)間的性質(zhì)的來構(gòu)造的, 如下是一棵區(qū)間[0, 3]的線段樹，每個[start, end]都是一個二叉樹中的節(jié)點涣达。
區(qū)間劃分大概就是上述的區(qū)間劃分在辆。可以看出每次都將區(qū)間的長度一分為二,數(shù)列長度為n,所以線段樹的高度是log(n),這是很多高效操作的基礎(chǔ)度苔。
上述的區(qū)間存儲的只是區(qū)間的左右邊界匆篓。我們可以將區(qū)間的最大值加入進(jìn)來,也就是樹中的Node需要存儲left，right左右子節(jié)點外寇窑，還需要存儲start, end, val區(qū)間的范圍和區(qū)間內(nèi)表示的值鸦概。
可以儲存不同的值，例如區(qū)間內(nèi)的最大值甩骏，最小值窗市，區(qū)間的求和等等。
因為每次將區(qū)間的長度一分為二,所有創(chuàng)造的節(jié)點個數(shù)饮笛，即底層有n個節(jié)點咨察，那么倒數(shù)第二次約n/2個節(jié)點，倒數(shù)第三次約n/4個節(jié)點福青，依次類推：
n + 1/2 * n + 1/4 * n + 1/8 * n + ...
= (1 + 1/2 + 1/4 + 1/8 + ...) * n
= 2n
所以構(gòu)造線段樹的時間復(fù)雜度和空間復(fù)雜度都為O(n)摄狱。
線段樹中的Node如何定義
二叉樹的節(jié)點區(qū)間定義，[start, end]代表節(jié)點的區(qū)間范圍无午，max 是節(jié)點在[start, end]區(qū)間上的最大值 left , right 是當(dāng)前節(jié)點區(qū)間劃分之后的左右節(jié)點區(qū)間：
// 節(jié)點區(qū)間定義
// [start, end] 代表節(jié)點的區(qū)間范圍
// max 是節(jié)點在(start,end)區(qū)間上的最大值
// left , right 是當(dāng)前節(jié)點區(qū)間劃分之后的左右節(jié)點區(qū)間
public class SegmentTreeNode {
public int start, end, max;
public SegmentTreeNode left, right;
public SegmentTreeNode(int start, int end, int max) {
this.start = start;
this.end = end;
this.max = max
this.left = this.right = null;
}
}
線段樹區(qū)間最大值維護(hù)
給定一個區(qū)間媒役，我們要維護(hù)線段樹中存在的區(qū)間中最大的值。這將有利于我們高效的查詢?nèi)魏螀^(qū)間的最大值宪迟。給出A數(shù)組酣衷，基于A數(shù)組構(gòu)建一棵維護(hù)最大值的線段樹，我們可以在O(logN)的復(fù)雜度內(nèi)查詢?nèi)我鈪^(qū)間的最大值：
比如原數(shù)組 A = [1, 4, 2, 3]
// 構(gòu)造的代碼及注釋
public SegmentTreeNode build(int[] A) {
// write your code here
return buildhelper(0, A.length - 1, A);
}
public SegmentTreeNode buildhelper(int left, int right, int[] A){
if(left > right){
return null;
}
SegmentTreeNode root = new SegmentTreeNode(left, right, A[left]); // 根據(jù)節(jié)點區(qū)間的左邊界的序列值為節(jié)點賦初值
if(left == right){
return root; // 如果左邊界和右邊界相等,節(jié)點左邊界的序列值就是線段樹節(jié)點的接節(jié)點值
}
int mid = (left + right) / 2; // 劃分當(dāng)前區(qū)間的左右區(qū)間
root.left = buildhelper(left, mid, A);
root.right = buildhelper(mid + 1, right, A);
root.max = Math.max(root.left.max, root.right.max); // 根據(jù)節(jié)點區(qū)間的左右區(qū)間的節(jié)點值得到當(dāng)前節(jié)點的節(jié)點值
return root;
}
舉一反三：
如果需要區(qū)間的最小值:
root.min = Math.min(root.left.min, root.right.min);
如果需要區(qū)間的和:
root.sum = root.left.sum + root.right.sum;
線段樹的單點更新
更新序列中的一個節(jié)點次泽，如何把這種變化體現(xiàn)到線段樹中去穿仪，例如，將序列中的第4個點A[3]更新為5, 要變動3個區(qū)間中的值,分別為[3,3],[2,3],[0,3]
提問：為什么需要更新這三個區(qū)間意荤？：因為只有這三個在線段樹中的區(qū)間牡借，覆蓋了3這個點。
更新所以需要從葉子節(jié)點一路走到根節(jié)點, 去更新線段樹上的值袭异。因為線段樹的高度為log(n),所以更新序列中一個節(jié)點的復(fù)雜度為log(n)钠龙。
// 單點更新的代碼及注釋
public void modify(SegmentTreeNode root, int index, int value) {
// write your code here
if(root.start == root.end && root.start == index) { // 找到被改動的葉子節(jié)點
root.max = value; // 改變value值
return ;
}
int mid = (root.start + root.end) / 2; // 將當(dāng)前節(jié)點區(qū)間分割為2個區(qū)間的分割線
if(index <= mid){ // 如果index在當(dāng)前節(jié)點的左邊
modify(root.left, index, value); // 遞歸操作
root.max = Math.max(root.right.max, root.left.max); // 可能對當(dāng)前節(jié)點的影響
}
else { // 如果index在當(dāng)前節(jié)點的右邊
modify(root.right, index, value); // 遞歸操作
root.max = Math.max(root.left.max, root.right.max); // 可能對當(dāng)前節(jié)點的影響
}
return ;
}
線段樹的區(qū)間查詢
線段樹的區(qū)間查詢操作就是將當(dāng)前區(qū)間分解為較小的子區(qū)間,然后由子區(qū)間的最大值就可以快速得到需要查詢區(qū)間的最大值。
query(1,3) = max(query(1,1),query(2,3)) = max(4,3) = 4
任意長度的線段，最多被拆分成logn條線段樹上存在的線段碴里，所以查詢的時間復(fù)雜度為O(log(n))沈矿。
// 區(qū)間查詢的代碼及注釋
public int query(TreeNode root, int start, int end) {
if (start <= root.start && root.end <= end) {
// 如果查詢區(qū)間在當(dāng)前節(jié)點的區(qū)間之內(nèi),直接輸出結(jié)果
return root.max;
}
int mid = (root.start + root.end) / 2; // 將當(dāng)前節(jié)點區(qū)間分割為左右2個區(qū)間的分割線
int ans = Integer.MIN_VALUE; // 給結(jié)果賦初值
if (mid >= start) { // 如果查詢區(qū)間和左邊節(jié)點區(qū)間有交集,則尋找查詢區(qū)間在左邊區(qū)間上的最大值
ans = Math.max(ans, query(root.left, start, end));
}
if (mid + 1 <= end) { // 如果查詢區(qū)間和右邊節(jié)點區(qū)間有交集,則尋找查詢區(qū)間在右邊區(qū)間上的最大值
ans = Math.max(ans, query(root.right, start, end));
}
return ans; // 返回查詢結(jié)果
}
Segment Tree 線段樹 的數(shù)組實現(xiàn)
雖然 Segment Tree 線段樹邏輯上是一棵二叉樹，但是實際存儲時可以通過數(shù)組來實現(xiàn)咬腋，通過父子節(jié)點的下標(biāo)的數(shù)值關(guān)系可以訪問父節(jié)點的子節(jié)點羹膳。
例如通過如下代碼將一個數(shù)組轉(zhuǎn)換為一個 Segment Tree：
// a segment tree
private int[] seg;
// the element count
private int n;
public NumArray(int[] nums) {
n = nums.length;
if(n > 0) {
seg = new int[4 * n];
build(nums, 0, n - 1, 0);
}
}
// build segment tree, set the value of seg[idx]
public void build(int[] nums, int start, int end, int idx) {
if(start == end) {
seg[idx] = nums[start];
}
else {
int mid = (start + end) / 2;
// build left tree
build(nums, start, mid, 2 * idx + 1);
// build right tree
build(nums, mid + 1, end, 2 * idx + 2);
seg[idx] = seg[2 * idx + 1] + seg[2 * idx + 2];
}
}
更新元素：更新元素需要更新兩個地方，一是原數(shù)組對應(yīng)的下標(biāo)的值根竿，另外一個是包含了這個元素的 Segment Tree 中的節(jié)點的值陵像。具體也是通過遞歸實現(xiàn)：
public void update(int i, int val) {
update(0, n - 1, i, val, 0);
}
public void update(int start, int end, int i, int val, int idx) {
// leaf node. update element.
if (start == end) {
seg[idx] = val;
return;
}
int mid = (start + end) / 2;
// left tree
if (i <= mid) {
update(start, mid, i, val, 2 * idx + 1);
}
// right tree
else {
update(mid + 1, end, i, val, 2 * idx + 2);
}
seg[idx] = seg[2 * idx + 1] + seg[2 * idx + 2];
}
區(qū)間求和：區(qū)間求和也是通過遞歸實現(xiàn)，關(guān)鍵在于根據(jù)當(dāng)前節(jié)點表示的范圍以及需要求的區(qū)間的范圍的關(guān)系進(jìn)行求和：
public int sumRange(int i, int j) {
return sumRange(0, n - 1, i, j, 0);
}
public int sumRange(int start, int end, int i, int j, int idx) {
// segment completely outside range, represents a null node
if (start > j || end < i)
return 0;
// segment completely inside range
if (i <= start && j >= end)
return seg[idx];
int mid = (start + end) / 2;
return sumRange(start, mid, i, j, 2 * idx + 1) +
sumRange(mid + 1, end, i, j, 2 * idx + 2);
}
Segment Tree 線段樹 使用示例
LeetCode 題目：
LintCode題目：207. 區(qū)間求和 II
在類的構(gòu)造函數(shù)中給一個整數(shù)數(shù)組, 實現(xiàn)兩個方法 query(start, end) 和 modify(index, value):
- 對于
query(start, end), 返回數(shù)組中下標(biāo)start到end的 和寇壳。 - 對于
modify(index, value), 修改數(shù)組中下標(biāo)為index上的數(shù)為value醒颖。
樣例
給定數(shù)組 A = [1,2,7,8,5].
query(0, 2), 返回 10.
modify(0, 4), 將 A[0] 修改為 4.
query(0, 1), 返回 6.
modify(2, 1), 將 A[2] 修改為 1.
query(2, 4), 返回 14.
/* you may need to use some attributes here */
class SegmentTreeNode {
public int start, end;
public int sum;
public SegmentTreeNode left, right;
public SegmentTreeNode(int start, int end, int sum) {
this.start = start;
this.end = end;
this.sum = sum;
this.left = this.right = null;
}
}
SegmentTreeNode root;
public SegmentTreeNode build(int start, int end, int[] A) {
// write your code here
if(start > end) { // check core case
return null;
}
SegmentTreeNode root = new SegmentTreeNode(start, end, 0);
if(start != end) {
int mid = (start + end) / 2;
root.left = build(start, mid, A);
root.right = build(mid+1, end, A);
root.sum = root.left.sum + root.right.sum;
} else {
root.sum = A[start];
}
return root;
}
public int querySegmentTree(SegmentTreeNode root, int start, int end) {
// write your code here
if(start == root.start && root.end == end) { // 相等
return root.sum;
}
int mid = (root.start + root.end)/2;
int leftsum = 0, rightsum = 0;
// 左子區(qū)
if(start <= mid) {
if( mid < end) { // 分裂
leftsum = querySegmentTree(root.left, start, mid);
} else { // 包含
leftsum = querySegmentTree(root.left, start, end);
}
}
// 右子區(qū)
if(mid < end) { // 分裂 3
if(start <= mid) {
rightsum = querySegmentTree(root.right, mid+1, end);
} else { // 包含
rightsum = querySegmentTree(root.right, start, end);
}
}
// else 就是不相交
return leftsum + rightsum;
}
public void modifySegmentTree(SegmentTreeNode root, int index, int value) {
// write your code here
if(root.start == index && root.end == index) { // 查找到
root.sum = value;
return;
}
// 查詢
int mid = (root.start + root.end) / 2;
if(root.start <= index && index <=mid) {
modifySegmentTree(root.left, index, value);
}
if(mid < index && index <= root.end) {
modifySegmentTree(root.right, index, value);
}
//更新
root.sum = root.left.sum + root.right.sum;
}
/**
* @param A: An integer array
*/
public Solution(int[] A) {
// write your code here
root = build(0, A.length-1, A);
}
/**
* @param start, end: Indices
* @return: The sum from start to end
*/
public long query(int start, int end) {
// write your code here
return querySegmentTree(root, start ,end);
}
/**
* @param index, value: modify A[index] to value.
*/
public void modify(int index, int value) {
// write your code here
modifySegmentTree(root, index, value);
}
}
LeetCode題目：315. Count of Smaller Numbers After Self
You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
Example:
Given nums = [5, 2, 6, 1]
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].
class Solution {
class TreeNode {
int val;
int count; // **從左往右**，小于該val的數(shù)字的數(shù)目
int duplicates; // 該val對應(yīng)的數(shù)字的重復(fù)個數(shù)
TreeNode left;
TreeNode right;
TreeNode(int val) {
this.val = val;
}
}
public List<Integer> countSmaller(int[] nums) {
Integer[] result = new Integer[nums.length];
TreeNode root = null;
// 從右往左以此插入數(shù)字
for(int i = nums.length - 1; i >= 0; i--) {
root = insert(nums[i], root, result, i, 0);
}
return Arrays.asList(result);
}
// 將值為num的節(jié)點插入
public TreeNode insert(int num, TreeNode node, Integer[] result, int idx, int preSum) {
// 創(chuàng)建節(jié)點
if(node == null) {
node = new TreeNode(num);
node.count = 0;
node.duplicates = 1;
result[idx] = preSum;
}
// 更新節(jié)點
else if (node.val == num) {
node.duplicates++;
result[idx] = preSum + node.count;
}
// 在左子樹添加
else if (node.val > num) {
node.count++;
node.left = insert(num, node.left, result, idx, preSum);
}
// 在右子樹添加
else {
node.right = insert(num, node.right, result, idx, preSum + node.duplicates + node.count);
}
return node;
}
}
總結(jié) - 線段樹問題解決的框架
-
如果問題帶有區(qū)間操作壳炎，或者可以轉(zhuǎn)化成區(qū)間操作泞歉，可以嘗試往線段樹方向考慮
- 從面試官給的題目中抽象問題，將問題轉(zhuǎn)化成一列區(qū)間操作匿辩，注意這步很關(guān)鍵
-
當(dāng)我們分析出問題是一些列區(qū)間操作的時候
- 對區(qū)間的一個點的值進(jìn)行修改
- 對區(qū)間的一段值進(jìn)行統(tǒng)一的修改
- 詢問區(qū)間的和
- 詢問區(qū)間的最大值腰耙、最小值
我們都可以采用線段樹來解決這個問題
套用我們前面講到的經(jīng)典步驟和寫法，即可在面試中完美的解決這些題目铲球！
什么情況下挺庞，無法使用線段樹？
如果我們刪除或者增加區(qū)間中的元素稼病，那么區(qū)間的大小將發(fā)生變化选侨，此時是無法使用線段樹解決這種問題的。
引用：
Segment Tree 簡介
A Recursive approach to Segment Trees, range sum queries & lazy propagation
線段樹入門教程
