作者:一曲无痕奈何
链接:https://blog.csdn.net/qq_41479464/article/details/88586512
来源:CSDN
注意区间的改变!(原来的部分被重新区间的染色覆盖了)
注意以求和问题为列,把整个区间分为很多段,当你求那一段时候,这样直接就可以拿。
每一个孩子区间都是相应的父节点的半段
注意叶子节点不一定在最后一层
定义一个接口(融合器就是方便我对区间的操作)
public interface Merge<E> {
E merge(E a,E b);
}
public class SegMentTree<E> {
private E[] tree;
private E data[] ;//存储一个副本
private Merge<E> merge;//用户构造好这个线段树时候同时构造好融合器
//考虑整个区间
public SegMentTree(E[] arr,Merge<E>merge){ //传入一个融合器
this.merge = merge;
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,data.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-l)/2;//这样定义中间位置放置溢出
buildSegMentTree(leftTreeIndex,l,mid); //创建左子树
buildSegMentTree(rightTreeIndex,mid+1,r);//创建右子树
//这个E的类型无法用求和
tree[treeIndex] = merge.merge(tree[leftTreeIndex],tree[rightTreeIndex]); //求和
//tree[treeIndex] = Math.max(tree[leftTreeIndex],tree[rightTreeIndex]); //求两者之间的最大值
}
public int getSize(){
return data.length;
}
public E get(int index){
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();
}
}
class Main{
public static void main(String [] args){
Integer nums[] = {1,2,3,4,-5,-9,10,125,32};
//SegMentTree<Integer> segMentTree = new SegMentTree<Integer>(nums,(a,b)->a+b);
SegMentTree<Integer> segMentTree = new SegMentTree<Integer>(nums, new Merge<Integer>() {
@Override
public Integer merge(Integer a, Integer b) {
return a+b;
}
});
System.out.println(segMentTree);
}
}
定义一个接口(融合器就是方便我对区间的操作)
public interface Merge<E> {
E merge(E a,E b);
}
public class SegMentTree<E> {
private E[] tree;
private E data[] ;//存储一个副本
private Merge<E> merge;//用户构造好这个线段树时候同时构造好融合器
//考虑整个区间
public SegMentTree(E[] arr,Merge<E>merge){ //传入一个融合器
this.merge = merge;
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,data.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-l)/2;//这样定义中间位置放置溢出
buildSegMentTree(leftTreeIndex,l,mid); //创建左子树
buildSegMentTree(rightTreeIndex,mid+1,r);//创建右子树
//这个E的类型无法用求和
tree[treeIndex] = merge.merge(tree[leftTreeIndex],tree[rightTreeIndex]); //求和
//tree[treeIndex] = Math.max(tree[leftTreeIndex],tree[rightTreeIndex]); //求两者之间的最大值
}
public int getSize(){
return data.length;
}
public E get(int index){
return data[index];
}
private int leftChild(int index){
return 2*index+1;
}
private int rightChild(int index){
return 2*index+2;
}
//返回区间[queryL,queryR]的值
public E query(int queryL,int queryR){
return query(0,0,data.length-1,queryL,queryR);
}
//在以treeID为根的线段树中[l...r]的范围里,搜索区间[queryl,queryr]的值
private E query(int treeIndex,int l,int r,int queryL,int queryR){
if(l==queryL&&r==queryR)
return tree[treeIndex];
int mid = l + (r-l)/2;
int leftTreeIndex = leftChild(treeIndex);
int rightTreeIndex = rightChild(treeIndex);
if (queryL>=mid+1){
return query(rightTreeIndex,mid+1,r,queryL,queryR);
}else if (queryR<=mid){
return query(leftTreeIndex,l,mid,queryL,queryR);
}
//分散在两个区间
E leftResult = query(leftTreeIndex,l,mid,queryL,queryR);
E rightResult = query(rightTreeIndex,mid+1,r,mid+1,queryR);
return merge.merge(leftResult,rightResult);
}
@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();
}
}
class Main{
public static void main(String [] args){
Integer nums[] = {1,2,3,4,-5,-9,10,125,32};
//SegMentTree<Integer> segMentTree = new SegMentTree<Integer>(nums,(a,b)->a+b);
SegMentTree<Integer> segMentTree = new SegMentTree<Integer>(nums, new Merge<Integer>() {
@Override
public Integer merge(Integer a, Integer b) {
return a+b;
}
});
System.out.println(segMentTree);
System.out.println(segMentTree.query(0,2));
}
}
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论