線段樹(又稱區(qū)間樹), 是一種高級數(shù)據(jù)結(jié)構(gòu)泽谨，他可以支持這樣的一些操作:
- 查找給定的點包含在了哪些區(qū)間內(nèi)
- 查找給定的區(qū)間包含了哪些點
線段樹的構(gòu)造
題目
線段樹是一棵二叉樹璧榄，他的每個節(jié)點包含了兩個額外的屬性start和end用于表示該節(jié)點所代表的區(qū)間。start和end都是整數(shù)吧雹，并按照如下的方式賦值:
- 根節(jié)點的 start 和 end 由 build 方法所給出骨杂。
- 對于節(jié)點 A 的左兒子，有 start=A.left, end=(A.left + A.right) / 2雄卷。
- 對于節(jié)點 A 的右兒子搓蚪，有 start=(A.left + A.right) / 2 + 1, end=A.right。
- 如果 start 等于 end, 那么該節(jié)點是葉子節(jié)點丁鹉，不再有左右兒子妒潭。
實現(xiàn)一個 build 方法，接受 start 和 end 作為參數(shù), 然后構(gòu)造一個代表區(qū)間 [start, end] 的線段樹揣钦，返回這棵線段樹的根雳灾。
代碼
/**
* Definition of SegmentTreeNode:
* public class SegmentTreeNode {
* public int start, end;
* public SegmentTreeNode left, right;
* public SegmentTreeNode(int start, int end) {
* this.start = start, this.end = end;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
*@param start, end: Denote an segment / interval
*@return: The root of Segment Tree
*/
public SegmentTreeNode build(int start, int end) {
// write your code here
if(start > end) { // check core case
return null;
}
SegmentTreeNode root = new SegmentTreeNode(start, end);
if(start < end) {
int mid = (start + end) / 2;
root.left = build(start, mid);
root.right = build(mid+1, end);
}
return root;
}
}
線段樹的構(gòu)造 II
題目
跟上題類似，增加一個屬性max冯凹，記錄區(qū)間最大值
代碼
/**
* Definition of SegmentTreeNode:
* 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;
* }
* }
*/
public class Solution {
/**
*@param A: a list of integer
*@return: The root of Segment Tree
*/
public SegmentTreeNode build(int[] A) {
// write your code here
return buildTree(0, A.length - 1, A);
}
public SegmentTreeNode buildTree(int start, int end, int[] A) {
if (start > end)
return null;
if (start == end) {
return new SegmentTreeNode(start, end, A[start]);
}
SegmentTreeNode node = new SegmentTreeNode(start, end, A[start]);
int mid = (start + end) / 2;
node.left = this.buildTree(start, mid, A);
node.right = this.buildTree(mid + 1, end, A);
node.max = Math.max(node.left.max, node.right.max);
return node;
}
}
線段樹的查詢
題目
對于一個有n個數(shù)的整數(shù)數(shù)組谎亩，在對應(yīng)的線段樹中, 根節(jié)點所代表的區(qū)間為0-n-1, 每個節(jié)點有一個額外的屬性max，值為該節(jié)點所代表的數(shù)組區(qū)間start到end內(nèi)的最大值谈竿。
為SegmentTree設(shè)計一個 query 的方法团驱，接受3個參數(shù)root, start和end，線段樹root所代表的數(shù)組中子區(qū)間[start, end]內(nèi)的最大值空凸。
樣例
對于數(shù)組 [1, 4, 2, 3], 對應(yīng)的線段樹為：
query(root, 1, 1), return 4
query(root, 1, 2), return 4
query(root, 2, 3), return 3
query(root, 0, 2), return 4
代碼
/**
* Definition of SegmentTreeNode:
* 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;
* }
* }
*/
public class Solution {
/**
*@param root, start, end: The root of segment tree and
* an segment / interval
*@return: The maximum number in the interval [start, end]
*/
public int query(SegmentTreeNode root, int start, int end) {
// write your code here
if(root == null)
{
return Integer.MIN_VALUE;
}
if(start == root.start && root.end == end) { // 相等
return root.max;
}
int mid = (root.start + root.end)/2;
int leftmax = Integer.MIN_VALUE, rightmax = Integer.MIN_VALUE;
// 左子區(qū)
if(start <= mid) {
if( mid < end) { // 分裂
leftmax = query(root.left, start, mid);
} else { // 包含
leftmax = query(root.left, start, end);
}
// leftmax = query(root.left, start, Math.min(mid,end));
}
// 右子區(qū)
if(mid < end) { // 分裂 3
if(start <= mid) {
rightmax = query(root.right, mid+1, end);
} else { // 包含
rightmax = query(root.right, start, end);
}
//rightmax = query(root.right, Math.max(mid+1,start), end);
}
// else 就是不相交
return Math.max(leftmax, rightmax);
}
}
線段樹查詢 II
題目
對于一個數(shù)組，我們可以對其建立一棵 線段樹, 每個結(jié)點存儲一個額外的值 count 來代表這個結(jié)點所指代的數(shù)組區(qū)間內(nèi)的元素個數(shù). (數(shù)組中并不一定每個位置上都有元素)
實現(xiàn)一個 query 的方法寸痢，該方法接受三個參數(shù) root, start 和 end, 分別代表線段樹的根節(jié)點和需要查詢的區(qū)間呀洲，找到數(shù)組中在區(qū)間[start, end]內(nèi)的元素個數(shù)。
樣例
對于數(shù)組 [0, 空啼止，2, 3], 對應(yīng)的線段樹為：
query(1, 1), return 0
query(1, 2), return 1
query(2, 3), return 2
query(0, 2), return 2
代碼
/**
* Definition of SegmentTreeNode:
* public class SegmentTreeNode {
* public int start, end, count;
* public SegmentTreeNode left, right;
* public SegmentTreeNode(int start, int end, int count) {
* this.start = start;
* this.end = end;
* this.count = count;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
*@param root, start, end: The root of segment tree and
* an segment / interval
*@return: The count number in the interval [start, end]
*/
public int query(SegmentTreeNode root, int start, int end) {
// write your code here
if(start > end || root==null)
return 0;
if(start <= root.start && root.end <= end) { // 相等
return root.count;
}
int mid = (root.start + root.end)/2;
int leftsum = 0, rightsum = 0;
// 左子區(qū)
if(start <= mid) {
if( mid < end) { // 分裂
leftsum = query(root.left, start, mid);
} else { // 包含
leftsum = query(root.left, start, end);
}
}
// 右子區(qū)
if(mid < end) { // 分裂 3
if(start <= mid) {
rightsum = query(root.right, mid+1, end);
} else { // 包含
rightsum = query(root.right, start, end);
}
}
// else 就是不相交
return leftsum + rightsum;
}
}
線段樹的修改
題目
對于一棵 最大線段樹, 每個節(jié)點包含一個額外的 max 屬性道逗，用于存儲該節(jié)點所代表區(qū)間的最大值。
設(shè)計一個 modify 的方法献烦，接受三個參數(shù) root滓窍、 index 和 value。該方法將 root 為跟的線段樹中 [start, end] = [index, index] 的節(jié)點修改為了新的 value 巩那，并確保在修改后吏夯，線段樹的每個節(jié)點的 max 屬性仍然具有正確的值此蜈。
樣例
對于線段樹:
代碼
/**
* Definition of SegmentTreeNode:
* 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;
* }
* }
*/
public class Solution {
/**
*@param root, index, value: The root of segment tree and
*@ change the node's value with [index, index] to the new given value
*@return: void
*/
public void modify(SegmentTreeNode root, int index, int value) {
// write your code here
if(root.start >= index && root.end <= index) { // 查找到
root.max = value;
return;
}
// 查詢
int mid = (root.start + root.end) / 2;
if(root.start <= index && index <=mid) {
modify(root.left, index, value);
}
if(mid < index && index <= root.end) {
modify(root.right, index, value);
}
//更新
root.max = Math.max(root.left.max, root.right.max);
}
}
