Segment Tree 线段树算法（java）

**线段树算法 (Segment Tree)**
=====================================线段树是一种用于解决区间查询问题的数据结构。它通过将原始数组分成多个子数组，分别存储在不同的节点中，从而实现快速地对整个数组进行范围内的操作。

**线段树的定义**
-----------------

线段树是由一棵二叉树组成，每个节点代表一个区间。每个节点包含以下信息：

* `start`: 区间的起始索引* `end`: 区间的结束索引* `sum`: 区间内所有元素的和（或其他相关信息）

**线段树的构建**
-----------------

构建线段树需要将原始数组分成多个子数组，并分别存储在不同的节点中。具体步骤如下：

1. 将原始数组中的每个元素作为一个区间，存储在对应的节点中。
2. 对于每个节点，其左孩子代表该区间的左半部分（从 `start` 到 `(start + end) /2`），其右孩子代表该区间的右半部分（从 `(start + end) /2 +1` 到 `end`）。

**线段树的更新**
-----------------

当原始数组中的某个元素被修改时，需要更新相应的节点。具体步骤如下：

1. 找到该元素所在的区间。
2. 更新该区间内所有元素的和（或其他相关信息）。
3. 递归地向上更新父节点。

**线段树的查询**
-----------------

当需要对原始数组进行范围内的操作时，可以使用线段树来实现。具体步骤如下：

1. 找到该区间所在的叶子结点。
2. 逆向递归地向上更新父节点，直到找到根结点。

**Java 实现**
--------------

以下是 Java 中线段树算法的实现：

javapublic class SegmentTree {
 private int[] tree;
 private int n;

 public SegmentTree(int[] arr) {
 this.n = arr.length;
 this.tree = new int[4 * n];
 build(arr,0, n -1,0);
 }

 // 构建线段树 private void build(int[] arr, int start, int end, int index) {
 if (start == end) {
 tree[index] = arr[start];
 } else {
 int mid = (start + end) /2;
 build(arr, start, mid,2 * index +1);
 build(arr, mid +1, end,2 * index +2);
 tree[index] = tree[2 * index +1] + tree[2 * index +2];
 }
 }

 // 更新线段树 public void update(int i, int val) {
 update(i, val,0, n -1,0);
 }

 private void update(int i, int val, int start, int end, int index) {
 if (start == end && start == i) {
 tree[index] = val;
 } else {
 int mid = (start + end) /2;
 if (i <= mid) {
 update(i, val, start, mid,2 * index +1);
 } else {
 update(i, val, mid +1, end,2 * index +2);
 }
 tree[index] = tree[2 * index +1] + tree[2 * index +2];
 }
 }

 // 查询线段树 public int query(int start, int end) {
 return query(0, n -1, start, end,0);
 }

 private int query(int start, int end, int rangeStart, int rangeEnd, int index) {
 if (rangeStart > end || rangeEnd < start) {
 return0;
 } else if (start >= rangeStart && end <= rangeEnd) {
 return tree[index];
 } else {
 int mid = (start + end) /2;
 return query(start, mid, rangeStart, rangeEnd,2 * index +1)
 + query(mid +1, end, rangeStart, rangeEnd,2 * index +2);
 }
 }

 public static void main(String[] args) {
 int[] arr = {1,3,5,7,9};
 SegmentTree tree = new SegmentTree(arr);

 System.out.println(tree.query(0,4)); // 输出:25 tree.update(2,10);
 System.out.println(tree.query(0,4)); // 输出:35 }
}

javapublic static void main(String[] args) {
 int[] arr = {1,3,5,7,9};
 SegmentTree tree = new SegmentTree(arr);

 System.out.println(tree.query(0,4)); // 输出:25 tree.update(2,10);
 System.out.println(tree.query(0,4)); // 输出:35}