线段树怎么写java
时间: 2023-10-13 13:55:35 浏览: 47
线段树(Segment Tree)是一种常用的数据结构,用于解决区间查询问题。下面是一个简单的线段树的实现示例:
```java
class SegmentTree {
int[] tree;
int n;
public SegmentTree(int[] nums) {
n = nums.length;
tree = new int[4 * n];
buildTree(nums, 0, 0, n - 1);
}
private void buildTree(int[] nums, int index, int start, int end) {
if (start == end) {
tree[index] = nums[start];
return;
}
int mid = start + (end - start) / 2;
buildTree(nums, 2 * index + 1, start, mid);
buildTree(nums, 2 * index + 2, mid + 1, end);
tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
}
public void update(int i, int val) {
updateHelper(0, 0, n - 1, i, val);
}
private void updateHelper(int index, int start, int end, int i, int val) {
if (start == end) {
tree[index] = val;
return;
}
int mid = start + (end - start) / 2;
if (i <= mid) {
updateHelper(2 * index + 1, start, mid, i, val);
} else {
updateHelper(2 * index + 2, mid + 1, end, i, val);
}
tree[index] = tree[2 * index + 1] + tree[2 * index + 2];
}
public int query(int left, int right) {
return queryHelper(0, 0, n - 1, left, right);
}
private int queryHelper(int index, int start, int end, int left, int right) {
if (left > end || right < start) {
return 0;
}
if (left <= start && right >= end) {
return tree[index];
}
int mid = start + (end - start) / 2;
int leftSum = queryHelper(2 * index + 1, start, mid, left, right);
int rightSum = queryHelper(2 * index + 2, mid + 1, end, left, right);
return leftSum + rightSum;
}
}
```
这是一个基本的线段树的实现,包含了建树、更新以及查询功能。你可以根据实际需求进行修改和扩展。希望对你有所帮助!
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![java](https://img-home.csdnimg.cn/images/20210720083646.png)