创建线段树
我们已经了解了什么是线段树,并且想把线段树看成满的二叉树,这种情况下用数组就可以存储线段树。
如果要考虑的区间有n个元素,数组开4*n的空间就可以承载整个线段树了,下面我们就具体的对这个4*n个空间里到底要存储什么才能构建线段树相应的逻辑进行介绍。
比如我们处理求和这个线段树,也就是说我们线段树的目的是为了查询区间中的元素和的操作,相应的每个节点存储的就是一个区间中所有元素的和。
如图:根节点存储的就是10个元素的和,左孩子存储的就是前五个元素的和,右孩子存储的是后五个元素的和,依次划分到叶子节点。
代码演示
完整的线段树创建代码
public class SegmentTree{ private E[] tree; private E[] data; private Merger merger; public SegmentTree(E[] arr, Merger merger){ this.merger = merger; data = (E[])new Object[arr.length]; for(int i = 0 ; i < arr.length ; i ++) data[i] = arr[i]; tree = (E[])new Object[4 * arr.length]; buildSegmentTree(0, 0, arr.length - 1); } // 在treeIndex的位置创建表示区间[l...r]的线段树 private void buildSegmentTree(int treeIndex, int l, int r){ if(l == r){ tree[treeIndex] = data[l]; return; } int leftTreeIndex = leftChild(treeIndex); int rightTreeIndex = rightChild(treeIndex); // int mid = (l + r) / 2; int mid = l + (r - l) / 2; buildSegmentTree(leftTreeIndex, l, mid); buildSegmentTree(rightTreeIndex, mid + 1, r); tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]); } public int getSize(){ return data.length; } public E get(int index){ if(index < 0 || index >= data.length) throw new IllegalArgumentException("Index is illegal."); return data[index]; } // 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的索引 private int leftChild(int index){ return 2*index + 1; } // 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的索引 private int rightChild(int index){ return 2*index + 2; } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append('['); for(int i = 0 ; i < tree.length ; i ++){ if(tree[i] != null) res.append(tree[i]); else res.append("null"); if(i != tree.length - 1) res.append(", "); } res.append(']'); return res.toString(); } }
程序第35行如果我们这样写是报错的,错误的原因在于我们这个类型E不一定定义了加法,所以我们不能保证加法一定是合法的。
对于我们之前的分析,如果这部分代码只写成加法代码,整个线段树的作用其实就局限住了,我们不希望我们线段树只能处理加法或者求区间的最大最小值,我们还是希望能自由的组合逻辑。
tree[treeIndex] = tree[leftTreeIndex]+tree[rightTreeIndex];
这种情况下我们可以创建一个新的接口Merger(融合器)
public interface Merger{ E merge(E a, E b); }
下面在main函数中测试一下
public class Main { public static void main(String[] args) { Integer[] nums = {-2, 0, 3, -5, 2, -1}; // SegmentTreesegTree = new SegmentTree<>(nums, // new Merger () { // @Override // public Integer merge(Integer a, Integer b) { // return a + b; // } // }); SegmentTree segTree = new SegmentTree<>(nums, (a, b) -> a + b); System.out.println(segTree); } }
源码下载
[dm href='https://www.jikewenku.com/product/1487.html']下载地址[/dm]
导航目录
[dm href='https://www.jikewenku.com/geeknote/2241.html']查看导航[/dm]
常见问题FAQ
- 如果资源链接失效了怎么办?
- 本站用户分享的所有资源都有自动备份机制,如果资源链接失效,请联系本站客服QQ:2580505920更新资源地址。
- 如果用户分享的资源与描述不符怎么办?
- 如何分享个人资源获取赞助积分或其他奖励?
- 如果您发现了本资源有侵权行为怎么办?