力扣LeetCode，区域和检索 - 数组可修改

1 Given nums = [1, 3, 5]
2 
3 sumRange(0, 2) -> 9
4 update(1, 2)
5 sumRange(0, 2) -> 8

 1 package com.tree;
 2 
 3 /**
 4  * 融合器,可以处理任意类型
 5  *
 6  * @param <E>
 7  */
 8 public interface Merger<E> {
 9 
10     /**
11      * 就是将两个元素a,b转换成一个元素E
12      *
13      * @param a
14      * @param b
15      * @return
16      */
17     E merger(E a, E b);
18 }

  1 package com.tree;
  2 
  3 
  4 /**
  5  * 线段树
  6  */
  7 public class SegmentTree<E> {
  8 
  9     // 对于区间的每一个元素,有可能需要通过线段树来进行获取
 10     private E[] data;
 11 
 12     private E[] tree;// 这里面的变量tree,是用于将数组转换为二叉树的,看作是满二叉树.
 13 
 14     private Merger<E> merger;//融合器
 15 
 16 
 17     /**
 18      * 含参构造函数
 19      *
 20      * @param arr    要考察的整个区间的范围.
 21      * @param merger 融合器
 22      */
 23     public SegmentTree(E[] arr, Merger<E> merger) {
 24 
 25         this.merger = merger;
 26 
 27         // 通过创建Object的方式来创建E类型的数组
 28         data = (E[]) new Object[arr.length];
 29         // 循环遍历,将数组元素的值赋值给创建的数组
 30         for (int i = 0; i < arr.length; i++) {
 31             data[i] = arr[i];
 32         }
 33 
 34         // 此时,也要初始化一个线段树,数组长度是4倍的数组的大小,就可以存储所有的节点
 35         tree = (E[]) new Object[4 * arr.length];
 36 
 37         // 创建线段树,初始的时候根几点所对应的索引为0,
 38         // 初始的时候根节点即0索引位置的节点的左端点是0,右断点是尾部
 39         // 初始的时候根节点对应的区间就是我们data这个数组从头到尾,从最左端到最右端.
 40         buildSegmentTree(0, 0, arr.length - 1);
 41     }
 42 
 43     /**
 44      * 创建线段树,在treeIndex的位置创建表示区间[left...right]的线段树
 45      *
 46      * @param treeIndex 当前要创建的这个线段树的根节点所对应的索引
 47      * @param left      对于这个节点它所表示的那个线段或者区间的左右断点是什么,
 48      * @param right
 49      */
 50     private void buildSegmentTree(int treeIndex, int left, int right) {
 51         // 首先,考虑递归到底的情况
 52         // 如果区间长度为1的时候,只有一个元素,就是递归到底了
 53         if (left == right) {
 54             // 此时tree[treeIndex]线段树节点存储的就是元素的本身data[left]
 55             tree[treeIndex] = data[left];
 56             // tree[treeIndex] = data[right];
 57             return;
 58         }
 59 
 60         // 递归的第二部分
 61         // 如果此时left不等于right的时候,此时,left一定是小于right的,要表示的是一个区间的话
 62         // 首先要计算出表示一个区间的节点,这个节点一定会有左右孩子的.
 63         // 左孩子所对应的在线段树中的索引是leftTreeIndex
 64         int leftTreeIndex = this.leftChild(treeIndex);
 65         // 右孩子所对应的在线段树中的索引是rightTreeIndex
 66         int rightTreeIndex = this.rightChild(treeIndex);
 67 
 68         // 此时,要创建好这个节点的左右子树,对于创建这个节点的左右子树,我们已经知道了左右子树所对应的在数组中的
 69         // 那个索引,还需要知道对于这个左右子树来说,它相应的表示的区间范围,
 70 
 71         // 区间范围的计算
 72 //        int mid = (left + right) / 2;// 避免整形溢出
 73         int mid = left + (right - left) / 2;// 左边界,加上左右边界之间的距离除以2,得到的位置也是中间的位置.
 74         // 比如1-5, 1  2  3  4  5中间元素是3,那么就是1 + (5 - 1) /2 = 3.
 75 
 76         // 此时,有了中间位置之后,那么对于当前的treeIndex所在的这个节点,他表示从left到right这个区间
 77         // 它的左右子树表示的是什么区间呢,其实就是left 到 mid,mid + 1 到right.
 78         // 基于这两个区间再创建线段树,这是一个递归的过程
 79         // 创建左子树,从leftTreeIndex这个索引上创建从left 到 mid这个区间对应的线段树
 80         buildSegmentTree(leftTreeIndex, left, mid);
 81         // 创建右子树从rightTreeIndex这个索引上创建从mid + 1 到 right这个区间对应的线段树
 82         buildSegmentTree(rightTreeIndex, mid + 1, right);
 83 
 84         // 此时将treeIndex的左右子树创建好,最后在创建好两个子树之后
 85         // 此时考虑tree[treeIndex]的值应该是多少,是和业务有关系的,这里是求和
 86         // 这里的信息综合左右两个线段相应的信息来得到当前的这个更大的这个线段相应的信息.
 87         // 怎么综合是根据业务逻辑决定的.
 88         // 由于此时类型E不一定定义了加法,只能做加法还是减法还是求出最大值还是最小值等等.
 89         // 所以此时新增了融合器的功能,使用融合器进行操作
 90         tree[treeIndex] = merger.merger(tree[leftTreeIndex], tree[rightTreeIndex]);
 91         // 此时,递归创建线段树就完成了
 92     }
 93 
 94 
 95     /**
 96      * 获取指定索引的元素内容
 97      *
 98      * @param index
 99      * @return
100      */
101     public E get(int index) {
102         if (index < 0 || index >= data.length) {
103             throw new IllegalArgumentException("Index is illegal.");
104         }
105         return data[index];
106     }
107 
108     /**
109      * 关注的线段树区间一共有多少个元素
110      *
111      * @return
112      */
113     public int getSize() {
114         return data.length;
115     }
116 
117 
118     /**
119      * 返回完全二叉树的数组表示中,一个索引表示的元素的左孩子节点的索引.
120      *
121      * @param index
122      * @return
123      */
124     private int leftChild(int index) {
125         return 2 * index + 1;
126     }
127 
128     /**
129      * 返回完全二叉树的数组表示中,一个索引表示的元素的右孩子节点的索引.
130      *
131      * @param index
132      * @return
133      */
134     private int rightChild(int index) {
135         return 2 * index + 2;
136     }
137 
138     @Override
139     public String toString() {
140         StringBuilder stringBuilder = new StringBuilder();
141         stringBuilder.append('[');
142         for (int i = 0; i < tree.length; i++) {
143             if (tree[i] != null) {
144                 stringBuilder.append(tree[i]);
145             } else {
146                 stringBuilder.append("null");
147             }
148 
149             if (i != tree.length - 1) {
150                 stringBuilder.append(", ");
151             }
152         }
153         stringBuilder.append(']');
154         return stringBuilder.toString();
155     }
156 
157     /**
158      * 返回区间[queryLeft,queryRight]的值
159      *
160      * @param queryLeft  前闭区间，用户期望查询的区间左右两个边界
161      * @param queryRight 后闭区间
162      * @return
163      */
164     public E query(int queryLeft, int queryRight) {
165         // 进行边界检查
166         if (queryLeft < 0 || queryLeft >= data.length || queryRight < 0 || queryRight >= data.length || queryLeft > queryRight) {
167             throw new IllegalArgumentException("Index is illegal.");
168         }
169 
170         // 递归函数调用。根节点的索引是0，区间是从0开始，到data.lenght-1这个范围里面
171         // 还需要查询一个区间，这个区间是queryLeft到queryRight
172         return query(0, 0, data.length - 1, queryLeft, queryRight);
173     }
174 
175 
176     /**
177      * 在以treeId为根的线段树中[l...r]的范围里面，搜索区间[queryLeft...queryRight]的值
178      * <p>
179      * <p>
180      * 从线段树的根节点开始，根节点所在的索引treeIndex
181      * 相应的节点表示的是一个区间，节点表示的区间用left、right表示。
182      *
183      * @param treeIndex
184      * @param left      节点所表示的区间左边界left
185      * @param right     节点所表示的区间右边界left
186      * @return
187      */
188     private E query(int treeIndex, int left, int right, int queryLeft, int queryRight) {
189         // 需要注意的是我们做的线段树相关的操作，对于每一个treeIndex都传了对于这个treeIndex所在的节点
190         // 它所表示的区间范围是哪里left-right，对于这个区间范围，其实也可以包装成一个线段树中的一个节点类。
191         // 对于每一个节点存储它所对应的区间范围left-right，在这种情况下，直接传入treeIndex就行了，
192         // 通过这个索引就可以访问到这个节点，进而就可以访问到这个节点所表示的区间范围。
193 
194 
195         // 此处实现的方法是，在treeIndex所表示的这个区间范围，以参数的形式进行传递。
196         // int treeIndex, int left, int right三个参数都在表示当前的节点表示的相应的信息，
197         // 在这个节点中去查询queryLeft到queryRight这个用户关心区间。
198 
199 
200         // 递归的第一部分，终止条件，递归到底的情况
201         // 如果这个节点的左边界left和用户想要查询的左边界queryLeft、同时这个节点的有边界right和用户想要查询的有边界queryRight
202         // 重合的时候，就是递归到底的情况，这个节点的信息就是用户想要的信息。
203         if (left == queryLeft && right == queryRight) {
204             // 如果是的话，直接返回
205             return tree[treeIndex];
206         }
207 
208         // 递归的第二部分
209         // 计算中间的位置，此时，要继续到当前的这个节点的孩子节点去查找
210         int mid = left + (right - left) / 2;
211         // 到底是去到左孩子查找还是右孩子查找呢，还是两个孩子都要找一找呢，
212         // 首先计算左右两个孩子所对应的索引
213         int leftTreeChild = this.leftChild(treeIndex);
214         int rightTreeChild = this.rightChild(treeIndex);
215 
216         // 如果用户查询的左边界区间大于等于中间的位置即mid + 1，
217         // 对于当前的这个节点它将left-right这个范围分成了两个部分，两部分的中间是mid，
218         // 第一部分是left-mid，第二部分是mid-right。
219         // 如果用户关心的区间的左边界是大于等于中间的位置即mid + 1的话，
220         // 也就是用户关心的这个区间和这个节点的左孩子一点关系都没有的时候，左边这部分完全可以忽略了，
221         if (queryLeft >= mid + 1) {
222             // 此时去mid-right这个区间去查找queryLeft-queryRight这个区间的相应的结果。
223             return query(rightTreeChild, mid + 1, right, queryLeft, queryRight);
224         } else if (queryRight <= mid) {
225             // 用户关心的右边界小于中间的位置mid。把当前这个节点的区间一分为二，得到的这个mid中间位置。
226             // 此时，用户关心的这个区间和当前这个节点一分为二，和右边这一半，后半部分一点关系都没有的。
227             return query(leftTreeChild, left, mid, queryLeft, queryRight);
228         }
229 
230         // 如果，这两种情况都不是的话，意味着用户关注的区间queryLeft-queryRight既没有落到当前节点treeIndex
231         // 这个节点的左孩子所代表的那个节点，也没有完全落在右孩子所代表的那个节点中，
232         // 事实上，它有一部分落在左孩子那边，另外一部分落在右孩子那边。
233         // 在这种情况下，两边都需要查询一下。
234 
235         // 先去左孩子那边去查找，此时将queryLeft-queryRight这个区间拆分成了queryLeft-mid和
236         // mid + 1到queryRight这两个区间了。
237         // 此时，查找的queryLeft到mid的结果，存储到queryResult中。
238         E leftResult = query(leftTreeChild, left, mid, queryLeft, mid);
239         E rightResult = query(rightTreeChild, mid + 1, right, mid + 1, queryRight);
240 
241         // 如果用户关系的这部分区间有一部分在左节点，有另外一部分在右节点，此时，左右两边都需要进行查询。
242         // 查询完成以后就可以进行融合了。调用融合器进行融合。
243         return merger.merger(leftResult, rightResult);
244     }
245 
246 
247     /**
248      * 对线段树进行更新操作。
249      *
250      * <p>
251      * 将index位置的值，更新为e
252      *
253      * @param index
254      * @param e
255      */
256     public void set(int index, E e) {
257         // 对index合法性进行检测
258         if (index < 0 || index >= data.length) {
259             throw new IllegalArgumentException("Index is illegal.");
260         }
261 
262         // 索引index正常
263         // 此时，将线段树的data[index]这个index索引的值换成是e
264         data[index] = e;
265 
266         // 接下来对tree这个变量进行相应的更新操作了。
267         // 从根节点开始，所对应的这个区间从0到data.length-1,来更新index索引位置的元素更新为e。
268         this.set(0, 0, data.length - 1, index, e);
269     }
270 
271     /**
272      * 在以treeIndex为根的线段树中更新index的值为e
273      * <p>
274      * 递归函数修改，修改tree
275      * <p>
276      * 时间复杂度是O(logn)级别的。
277      * 从根节点开始，一直找到index这个位置的元素所在的那个叶子节点，这个高度是logn级别的。
278      *
279      * @param treeIndex 以treeIndex为根进行的线段树
280      * @param left      对于这个节点表示的是从left到right的值
281      * @param right
282      * @param index     在这个线段树中更新将index这个位置的元素为e
283      * @param e
284      */
285     public void set(int treeIndex, int left, int right, int index, E e) {
286         // 递归函数，递归到底的情况
287         if (left == right) {
288             // 此时，已经递归到底了，已经找到了要更新的节点了。
289             tree[treeIndex] = e;
290             return;
291         }
292 
293         // 否则，就是在线段树中去找index这个位置它对应的叶子的位置在哪里。
294         // 只有找到叶子节点才可以计算出根节点的值的。
295         // 线段树中每一个节点都是对应一个区间。
296         int mid = left + (right - left) / 2;
297         // 计算出对于treeIndex这个节点的左右孩子
298         // treeIndex这个左孩子的索引
299         int leftTreeIndex = leftChild(treeIndex);
300         // treeIndex这个右孩子的索引
301         int rightTreeIndex = rightChild(treeIndex);
302 
303         // 如果我们要找的index >= mid + 1的时候，此时只要去右子树继续寻找就行了
304         if (index >= mid + 1) {
305             // 此时,index在该节点对应的右子树所对应的区间
306             set(rightTreeIndex, mid + 1, right, index, e);
307         } else if (index <= mid) {
308             // 去左子树的所对应的区间去更新操作
309             set(leftTreeIndex, left, mid, index, e);
310         }
311 
312         // 对于线段树来说，我们最终找到了叶子节点，更新完了tree[treeIndex]之后，是不够的
313         // 相应的在返回去的过程中，这个叶子节点的父亲节点，这个父亲节点的父亲节点等一系列节点
314         // 都会受到牵连，因为这些节点描述的都是一个区间内相应的统计的值，而这些区间包含index这个
315         // 索引的元素，一旦index这个位置的元素发生了改变，那么它的祖辈节点相应所表示的区间包含这个index
316         // 其统计结果也要发生改变，所以最后的时候，在对每一个节点更新的时候，对这个节点的值tree[treeIndex]
317         // 也要进行一下更新，之间调用融合器进行更新。
318 
319         // 每次递归操作都进行了更新操作的。
320         tree[treeIndex] = merger.merger(tree[leftTreeIndex], tree[rightTreeIndex]);
321     }
322 
323 
324     public static void main(String[] args) {
325         Integer[] nums = {2, 0, 3, 5, 2, 1};
326 //        SegmentTree<Integer> segmentTree = new SegmentTree<Integer>(nums, new Merger<Integer>() {
327 //
328 //            /**
329 //             * 使用匿名内部类,来实现融合器
330 //             * @param a
331 //             * @param b
332 //             * @return
333 //             */
334 //            @Override
335 //            public Integer merger(Integer a, Integer b) {
336 //                return a + b;
337 //            }
338 //        });
339 
340 
341         //
342         SegmentTree<Integer> segmentTree = new SegmentTree<Integer>(nums,
343                 (a, b) -> a + b
344         );
345         System.out.println(segmentTree.toString());
346 
347         System.out.println();
348         // 线段树的查询
349         Integer query = segmentTree.query(0, 3);
350         System.out.println(query);
351     }
352 
353 }

 1 package com.leetcode;
 2 
 3 import com.tree.SegmentTree;
 4 
 5 /**
 6  * 线段树解决此问题
 7  * <p>
 8  * <p>
 9  * <p>
10  * 给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。
11  * <p>
12  * <p>
13  * 线段树的查询操作和修改操作的时间复杂度是O(logn)级别的。O(logn)远远快于O(n)级别的时间复杂度
14  * <p>
15  * <p>
16  * 线段树的创建的过程时间复杂度是O(n)的复杂度，更准确的说是O(4*n)的复杂度。
17  * <p>
18  * <p>
19  * 对于线段树来说，对于要考虑区间的这一种数据，尤其是想要查询区间的相关统计的信息的时候，
20  * 同时数据是动态的，不时要更新数据，线段树是一种很好的数据结构。
21  */
22 public class NumArray {
23 
24     // 线段树
25     private SegmentTree<Integer> segmentTree;
26 
27 
28     /**
29      * 给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
30      * <p>
31      * <p>
32      * sumRange(0, 2) -> 1
33      * sumRange(2, 5) -> -1
34      * sumRange(0, 5) -> -3
35      *
36      * @param nums
37      */
38     public NumArray(int[] nums) {
39         // 判断数组长度是否大于0，如果大于0就进行创建线段树
40         if (nums.length > 0) {
41             // 将int[]数组转换为Integer[]类型
42             Integer[] data = new Integer[nums.length];
43             for (int i = 0; i < data.length; i++) {
44                 data[i] = nums[i];
45             }
46 
47             // 开始初始化线段树
48             segmentTree = new SegmentTree<>(data, (a, b) -> a + b);
49         }
50     }
51 
52     /**
53      * 查询区间之间的和
54      * 查询操作，时间复杂度是O(logn)
55      *
56      * @param i
57      * @param j
58      * @return
59      */
60     public int sumRange(int i, int j) {
61         if (segmentTree == null) {
62             throw new IllegalArgumentException("Segment Tree is null.");
63         }
64 
65         return segmentTree.query(i, j);
66     }
67 
68 
69     /**
70      * <p>
71      * <p>
72      * 更新操作，时间复杂度是O(logn)
73      *
74      * @param i
75      * @param val
76      */
77     public void update(int i, int val) {
78         if (segmentTree == null) {
79             throw new IllegalArgumentException("Segment Tree is null.");
80         }
81 
82         // 直接调用线段树的更新操作即可
83         segmentTree.set(i, val);
84     }
85 
86     public static void main(String[] args) {
87         int[] nums = {-2, 0, 3, -5, 2, -1};
88         NumArray numArray = new NumArray(nums);
89         int sumRange = numArray.sumRange(0, 3);
90         System.out.println(sumRange);
91     }
92 
93 }