力扣LeetCode，区域和检索 - 数组不可变

1 给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
2 
3 sumRange(0, 2) -> 1
4 sumRange(2, 5) -> -1
5 sumRange(0, 5) -> -3

 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     public static void main(String[] args) {
248         Integer[] nums = {2, 0, 3, 5, 2, 1};
249 //        SegmentTree<Integer> segmentTree = new SegmentTree<Integer>(nums, new Merger<Integer>() {
250 //
251 //            /**
252 //             * 使用匿名内部类,来实现融合器
253 //             * @param a
254 //             * @param b
255 //             * @return
256 //             */
257 //            @Override
258 //            public Integer merger(Integer a, Integer b) {
259 //                return a + b;
260 //            }
261 //        });
262 
263 
264         //
265         SegmentTree<Integer> segmentTree = new SegmentTree<Integer>(nums,
266                 (a, b) -> a + b
267         );
268         System.out.println(segmentTree.toString());
269 
270         System.out.println();
271         // 线段树的查询
272         Integer query = segmentTree.query(0, 3);
273         System.out.println(query);
274     }
275 
276 }

 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  */
12 public class NumArray {
13 
14     // 线段树
15     private SegmentTree<Integer> segmentTree;
16 
17 
18     /**
19      * 给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
20      * <p>
21      * <p>
22      * sumRange(0, 2) -> 1
23      * sumRange(2, 5) -> -1
24      * sumRange(0, 5) -> -3
25      *
26      * @param nums
27      */
28     public NumArray(int[] nums) {
29         // 判断数组长度是否大于0，如果大于0就进行创建线段树
30         if (nums.length > 0) {
31             // 将int[]数组转换为Integer[]类型
32             Integer[] data = new Integer[nums.length];
33             for (int i = 0; i < data.length; i++) {
34                 data[i] = nums[i];
35             }
36 
37             // 开始初始化线段树
38             segmentTree = new SegmentTree<>(data, (a, b) -> a + b);
39         }
40     }
41 
42     /**
43      * 查询区间之间的和
44      *
45      * @param i
46      * @param j
47      * @return
48      */
49     public int sumRange(int i, int j) {
50         if (segmentTree == null) {
51             throw new IllegalArgumentException("Segment Tree is null.");
52         }
53 
54         return segmentTree.query(i, j);
55     }
56 
57     public static void main(String[] args) {
58         int[] nums = {-2, 0, 3, -5, 2, -1};
59         NumArray numArray = new NumArray(nums);
60         int sumRange = numArray.sumRange(0, 3);
61         System.out.println(sumRange);
62     }
63 
64 }

 1 package com.leetcode;
 2 
 3 
 4 /**
 5  * 预处理方式解决问题
 6  * <p>
 7  * <p>
 8  * <p>
 9  * 给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。
10  */
11 public class NumArray2 {
12 
13 
14     // sum[1]存储的就是前一个元素的和，sum[2]存储的就是前两个元素的和，以此类推。
15     // sum[0] = 0;
16     // 其实sum[i]本身存储的是num[0...i-1]的和。
17     private int[] sum; // 预处理静态处理，sum[i]存储前i个元素和。
18 
19     /**
20      * 给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
21      * <p>
22      * <p>
23      * sumRange(0, 2) -> 1
24      * sumRange(2, 5) -> -1
25      * sumRange(0, 5) -> -3
26      *
27      * @param nums
28      */
29     public NumArray2(int[] nums) {
30 
31         // sum本身的长度是nums.length + 1这么多个元素
32         // 最多可以取到sum[nums.length]，nums.length这么多元素相应的和
33         // 因为sum存储的元素有偏移，所以sum的长度是nums.length + 1。
34         // sum[0]存储的是0，sum[1]存储的是nums[0]，依次类推。
35         sum = new int[nums.length + 1];
36         // 初始化sum[0]=0; //O(n)的复杂度
37         for (int i = 1; i < sum.length; i++) {
38             // sum[i]存储的就是前i个元素的和。
39             sum[i] = sum[i - 1] + nums[i - 1];
40         }
41         // 此时已经就初始化完前i个元素的和。
42     }
43 
44     /**
45      * 查询区间之间的和
46      *
47      * @param i
48      * @param j
49      * @return
50      */
51     public int sumRange(int i, int j) {
52         // 注意，sum[j + 1]存储的就是0到j之间的元素的和。
53         // sum[i]存储的就是0-到i-1之间的元素的和。
54         // 相减之后剩下的就是i-j之间的和。
55         return sum[j + 1] - sum[i];//O(1)的复杂度
56     }
57 
58     public static void main(String[] args) {
59         int[] nums = {-2, 0, 3, -5, 2, -1};
60         NumArray2 numArray = new NumArray2(nums);
61         int sumRange = numArray.sumRange(0, 3);
62         System.out.println(sumRange);
63     }
64 
65 }