线段树（Segment Tree）是一种用于处理区间查询和更新问题的数据结构，特别是在需要对连续区间进行操作时非常有效。线段树可以快速地对区间求和、求最小值/最大值、判断某个值的存在性等问题进行响应。
线段树的特点：
- 高效性：线段树能够在对数时间内完成区间查询和更新操作。
- 空间优化：线段树通过节点合并来避免不必要的重复计算，节省了空间。
- 适用性：适用于需要对区间数据进行多次查询和更新的场景。
线段树的基本操作：
- 构建（Build）：从给定的数据数组出发，递归地构建线段树。
- 查询（Query）：根据给定的区间，在线段树中查找对应的合并结果。
- 更新（Update）：更新线段树中的某个位置的值，并递归地更新所有受影响的祖先节点。
线段树的Java实现：
class SegmentTree {
private int[] tree;
private int n;
public SegmentTree(int[] nums) {
if (nums.length > 0) {
n = nums.length;
tree = new int[n * 4];
build(nums, 0, 0, n - 1);
}
}
private void build(int[] nums, int treeIndex, int left, int right) {
if (left == right) {
tree[treeIndex] = nums[left];
return;
}
int mid = left + (right - left) / 2;
build(nums, 2 * treeIndex + 1, left, mid);
build(nums, 2 * treeIndex + 2, mid + 1, right);
tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
}
public int query(int left, int right) {
return query(0, 0, n - 1, left, right);
}
private int query(int treeIndex, int start, int end, int left, int right) {
if (left > end || start > end) {
return 0;
}
if (start >= left && end <= right) {
return tree[treeIndex];
}
int mid = start + (end - start) / 2;
return query(2 * treeIndex + 1, start, mid, left, right) +
query(2 * treeIndex + 2, mid + 1, end, left, right);
}
public void update(int index, int val) {
update(0, 0, n - 1, index, val);
}
private void update(int treeIndex, int start, int end, int index, int val) {
if (start == end) {
tree[treeIndex] = val;
return;
}
int mid = start + (end - start) / 2;
if (index <= mid) {
update(2 * treeIndex + 1, start, mid, index, val);
} else {
update(2 * treeIndex + 2, mid + 1, end, index, val);
}
tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
}
}
线段树的应用场景：
- 区间求和：快速计算给定区间内的元素和。
- 区间最小/最大值：查找给定区间内的最小值或最大值。
- 区间更新：更新某个区间内的元素值。
- 二维线段树：解决二维平面上的区间问题，如矩形区域的查询和更新。
面试大厂题示例：
-
区间求和：
描述：给定一个整数数组和一个区间列表，对于每个区间，计算其内所有元素的和。
示例：输入: nums = [1, 3, 5, 7, 9, 11], intervals = [[1, 3], [2, 5], [1, 1]] 输出: [16, 15, 3] -
区间最小值：
描述：给定一个整数数组和一个区间列表，对于每个区间，找到其中的最小值。
示例：输入: nums = [3, 4, 5, 1, 6, 2], intervals = [[2, 3], [1, 3], [0, 5]] 输出: [5, 1, 2] -
区间更新：
描述：给定一个整数数组和一个更新操作列表，对于每个更新操作，将其应用到数组的指定区间。
示例：输入: nums = [1, 3, 5, 7, 9, 11], updates = [[1, 2, 10], [3, 4, 20], [5, 5, 30]] 输出: [10, 13, 15, 30, 9, 11]
这些题目和源码展示了线段树在解决实际问题中的应用。在面试中，能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试！线段树是一种高效的数据结构，特别适合处理区间查询和更新问题。以下是三道可能出现在大厂面试中的与线段树相关的编程题目，以及相应的Java源码实现。
题目 1：区间求和
描述：
给定一个整数数组和一个区间列表，对于每个区间，计算其内所有元素的和。
示例：
输入: nums = [1, 3, 5, 7, 9, 11], intervals = [[1, 3], [2, 5], [1, 1]]
输出: [16, 15, 3]
Java 源码：
public class IntervalSumQuery {
private int[] tree;
private int n;
public IntervalSumQuery(int[] nums) {
n = nums.length;
tree = new int[n * 4];
buildTree(nums, 0, 0, n - 1);
}
private void buildTree(int[] nums, int treeIndex, int start, int end) {
if (start == end) {
tree[treeIndex] = nums[start];
return;
}
int mid = start + (end - start) / 2;
buildTree(nums, 2 * treeIndex + 1, start, mid);
buildTree(nums, 2 * treeIndex + 2, mid + 1, end);
tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
}
public int query(int start, int end) {
return query(0, 0, n - 1, start, end);
}
private int query(int treeIndex, int start, int end, int qStart, int qEnd) {
if (qStart > qEnd || start > qEnd || end < qStart) {
return 0;
}
if (start >= qStart && end <= qEnd) {
return tree[treeIndex];
}
int mid = start + (end - start) / 2;
int left = query(2 * treeIndex + 1, start, mid, qStart, qEnd);
int right = query(2 * treeIndex + 2, mid + 1, end, qStart, qEnd);
return left + right;
}
public static void main(String[] args) {
IntervalSumQuery query = new IntervalSumQuery(new int[]{1, 3, 5, 7, 9, 11});
int[] intervals = {{1, 3}, {2, 5}, {1, 1}};
int[] results = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
results[i] = query.intervalSumQuery(intervals[i][0], intervals[i][1]);
System.out.println("Sum of interval " + Arrays.toString(intervals[i]) + ": " + results[i]);
}
}
}
题目 2：区间最小值
描述：
给定一个整数数组和一个区间列表，找到每个区间内的最小值。
示例：
输入: nums = [3, 4, 5, 1, 6, 2], intervals = [[2, 3], [1, 3], [0, 5]]
输出: [5, 1, 2]
Java 源码：
public class IntervalMinQuery {
private int[] tree;
private int n;
public IntervalMinQuery(int[] nums) {
n = nums.length;
tree = new int[n * 4];
buildTree(nums, 0, 0, n - 1);
}
private void buildTree(int[] nums, int treeIndex, int start, int end) {
if (start == end) {
tree[treeIndex] = nums[start];
return;
}
int mid = start + (end - start) / 2;
buildTree(nums, 2 * treeIndex + 1, start, mid);
buildTree(nums, 2 * treeIndex + 2, mid + 1, end);
tree[treeIndex] = Math.min(tree[2 * treeIndex + 1], tree[2 * treeIndex + 2]);
}
public int query(int start, int end) {
return query(0, 0, n - 1, start, end);
}
private int query(int treeIndex, int start, int end, int qStart, int qEnd) {
if (qStart > qEnd || start > qEnd || end < qStart) {
return Integer.MAX_VALUE;
}
if (start >= qStart && end <= qEnd) {
return tree[treeIndex];
}
int mid = start + (end - start) / 2;
int left = query(2 * treeIndex + 1, start, mid, qStart, qEnd);
int right = query(2 * treeIndex + 2, mid + 1, end, qStart, qEnd);
return Math.min(left, right);
}
public static void main(String[] args) {
IntervalMinQuery query = new IntervalMinQuery(new int[]{3, 4, 5, 1, 6, 2});
int[] intervals = {{2, 3}, {1, 3}, {0, 5}};
int[] results = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
results[i] = query.intervalMinQuery(intervals[i][0], intervals[i][1]);
System.out.println("Minimum of interval " + Arrays.toString(intervals[i]) + ": " + results[i]);
}
}
}
题目 3：区间更新
描述：
给定一个整数数组和一个更新操作列表，对于每个更新操作，将其应用到数组的指定区间。
示例：
输入: nums = [1, 3, 5, 7, 9, 11], updates = [[1, 2, 10], [3, 4, 20], [5, 5, 30]]
输出: [10, 13, 15, 30, 9, 11]
Java 源码：文章来源：https://www.toymoban.com/news/detail-849046.html
public class IntervalUpdate {
private int[] tree;
private int n;
public IntervalUpdate(int[] nums) {
n = nums.length;
tree = new int[n * 4];
buildTree(nums, 0, 0, n - 1);
}
private void buildTree(int[] nums, int treeIndex, int start, int end) {
if (start == end) {
tree[treeIndex] = nums[start];
return;
}
int mid = start + (end - start) / 2;
buildTree(nums, 2 * treeIndex + 1, start, mid);
buildTree(nums, 2 * treeIndex + 2, mid + 1, end);
tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
}
public void update(int start, int end, int val) {
update(0, 0, n - 1, start, end, val);
}
private void update(int treeIndex, int start, int end, int qStart, int qEnd, int val) {
if (qStart > qEnd || start > qEnd || end < qStart) {
return;
}
if (start >= qStart && end <= qEnd) {
tree[treeIndex] = val;
return;
}
int mid = start + (end - start) / 2;
update(2 * treeIndex + 1, start, mid, qStart, qEnd, val);
update(2 * treeIndex + 2, mid + 1, end, qStart, qEnd, val);
tree[treeIndex] = tree[2 * treeIndex + 1] + tree[2 * treeIndex + 2];
}
public static void main(String[] args) {
IntervalUpdate update = new IntervalUpdate(new int[]{1, 3, 5, 7, 9, 11});
int[][] updates = {{1, 2, 10}, {3, 4, 20}, {5, 5, 30}};
for (int[] update : updates) {
update.update(update[0], update[1], update[2]);
System.out.println("Array after update " + Arrays.toString(update) + ": " + Arrays.toString(update.getArray()));
}
}
}
这些题目和源码展示了线段树在解决实际问题中的应用。在面试中，能够根据问题的特点选择合适的算法并实现其解决方案是非常重要的。希望这些示例能够帮助你更好地准备面试！文章来源地址https://www.toymoban.com/news/detail-849046.html
到了这里，关于Java线段树（含面试大厂题和源码）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
