- 線段樹(shù)的構(gòu)建
- 查詢(xún)
- 更新
- 指針實(shí)現(xiàn)
public class SegmentTreeNode {
public int start;
public int end;
public int max;
public SegmentTreeNode left;
public SegmentTreeNode right;
public SegmentTreeNode(int start, int end, int max) {
this.start = start;
this.end = end;
this.max = max;
this.left = null;
this.right = null;
}
//構(gòu)建線段樹(shù)
public SegmentTreeNode build(int[] nums) {
return buildHelper(0, nums.length - 1, nums);
}
public SegmentTreeNode buildHelper(int left, int right, int[] nums) {
if (left > right) {
return null;
}
//節(jié)點(diǎn)區(qū)間的值為其包含的元素的最大值康愤，取左邊界
SegmentTreeNode root = new SegmentTreeNode(left, right, nums[left]);
if (left == right) {
//遞歸終止條件
//如果只有一個(gè)元素针饥，則其左右子節(jié)點(diǎn)為空踪危，節(jié)點(diǎn)值為左邊界值
return root;
}
int mid = left + (right - left) / 2;
root.left = buildHelper(left, mid, nums);
root.right = buildHelper(mid + 1, right, nums);
//根據(jù)左右子節(jié)點(diǎn)的max更新當(dāng)前節(jié)點(diǎn)的max
root.max = Math.max(root.left.max, root.right.max);
return root;
}
//查詢(xún)區(qū)間[left, right]的最大值
public int query(SegmentTreeNode root, int start, int end) {
if (root == null || start > root.end || end < root.start) {
return Integer.MIN_VALUE;
}
//如果查詢(xún)區(qū)間包含當(dāng)前節(jié)點(diǎn)區(qū)間朗涩，則當(dāng)前節(jié)點(diǎn)即為所求
if (start <= root.start && root.end <= end) {
return root.max;
}
//遞歸查詢(xún)左右子節(jié)點(diǎn)
int mid = root.start + (root.end - root.start) / 2;
int leftMax = query(root.left, start, end);
int rightMax = query(root.right, start, end);
return Math.max(leftMax, rightMax);
}
//更新節(jié)點(diǎn)值 - 將索引index的值修改為val
public void modify(SegmentTreeNode root, int index, int val) {
if (root.start == root.end && root.start == index) {
root.max = val;
return;
}
//將當(dāng)前區(qū)間分割為左右兩個(gè)區(qū)間愿待，mid為分割線
int mid = root.start + (root.end - root.start)/ 2;
//判斷index落在哪個(gè)區(qū)間
if (index <= mid) {
//index在左子區(qū)間糠惫，遞歸更新左子區(qū)間
modify(root.left, index, val);
root.max = Math.max(root.left.max, root.right.max);
} else {
//index在右子區(qū)間实撒，遞歸更新右子區(qū)間
modify(root.right, index, val);
root.max = Math.max(root.left.max, root.right.max);
}
}
}
- 數(shù)組實(shí)現(xiàn) - 靈感來(lái)自正月點(diǎn)燈籠：
public class SegTree {
private int[] data;
private int[] tree;
public SegTree(int[] nums) {
this.data = nums;
this.tree = new int[nums.length * 4];
build(0, 0, nums.length - 1);
}
public void build(int node, int start, int end) {
if (start == end) {
tree[node] = data[start];
return;
}
// 計(jì)算出當(dāng)前節(jié)點(diǎn)的區(qū)間范圍
int mid = start + (end - start) / 2;
int leftNode = 2 * node + 1;
int rightNode = 2 * node + 2;
build(leftNode, start, mid);
build(rightNode, mid + 1, end);
tree[node] = tree[leftNode] + tree[rightNode];
}
public void update(int node, int start, int end, int index, int val) {
if (start == end){
tree[node] = val;
data[index] = val;
return;
}
// 計(jì)算出當(dāng)前節(jié)點(diǎn)的區(qū)間范圍
int mid = start + (end - start) / 2;
int leftNode = 2 * node + 1;
int rightNode = 2 * node + 2;
if (index >= start && index <= mid) {
update(leftNode, start, mid, index, val);
} else {
update(rightNode, mid + 1, end, index, val);
}
tree[node] = tree[leftNode] + tree[rightNode];
}
public int query(int node, int start, int end, int l, int r) {
//node：節(jié)點(diǎn)編號(hào)姊途；start，end：節(jié)點(diǎn)表示的區(qū)間知态；l捷兰，r：要查詢(xún)的區(qū)間
System.out.println("start: " + start + " end: " + end);
if (start > r || end < l) {
return 0;
}
if (l <= start && end <= r) {
return tree[node];
}
int mid = start + (end - start) / 2;
int leftNode = 2 * node + 1;
int rightNode = 2 * node + 2;
int sumLeft = query(leftNode, start, mid, l, r);
int sumRight = query(rightNode, mid + 1, end, l, r);
return sumLeft + sumRight;
}
public static void main(String[] args) {
int[] nums = {1, 3, 5, 7, 9, 11};
SegTree segTree = new SegTree(nums);
for (int i = 0; i < segTree.tree.length; i++) {
System.out.println(i + " - " + segTree.tree[i]);
}
segTree.update(0, 0, nums.length - 1, 0, 10);
System.out.println("Update 0 to 10:=======");
for (int i = 0; i < segTree.tree.length; i++) {
System.out.println(i + " - " + segTree.tree[i]);
}
System.out.println("Query 0 to 2:=======");
int query = segTree.query(0, 0, nums.length - 1, 0, 2);
System.out.println(query);
}
}
相關(guān)鏈接：
指針實(shí)現(xiàn)：構(gòu)建、搜索负敏、更新
https://baijiahao.baidu.com/s?id=1736339086704827934&wfr=spider&for=pc
數(shù)組實(shí)現(xiàn)
https://blog.csdn.net/myRealization/article/details/105130003
https://www.bilibili.com/video/BV1cb411t7AM/?spm_id_from=333.1007.top_right_bar_window_history.content.click&vd_source=ed89f81ec70f5a5933f8a8a3b71dbcc0
