【笔记】数据结构与算法之线段树
本帖最后由 QingYi. 于 2020-11-29 22:06 编辑Segment线段树的定义及其方法
public class SegmentTree<E> {
private E[] data;
private E[] tree;
private Merger<E> merger;
public SegmentTree(E[] arr,Merger<E> merger){
this.merger = merger;
int n = arr.length;
data = (E[])new Object;
for (int i = 0; i < n; i++) {
data = arr;
}
tree = (E[])new Object;
buildSegmentTree(0, 0, arr.length - 1);
}
public E query(int l , int r){
if (l < 0 || l >= data.length || r < 0 || r >= data.length || l > r) {
throw new IllegalArgumentException("index is illegal");
}
return query(0,0,data.length-1,l,r);
}
//在l到r 的区间里 搜索queryl到 queryr的值
private E query(int index, int l, int r, int queryL, int queryR) {
if(l==queryL && r == queryR){
return tree;
}
int mid = (l+r)>>1;
int leftIdx =leftChild(index);
int rightIdx =rightChild(index);
if (queryL>=mid+1){
return query(rightIdx,mid+1,r,queryL,queryR);
}else if (queryR<=mid){
return query(leftIdx,l,mid,queryL,queryR);
}
E leftRes = query(leftIdx, l, mid, queryL, mid);
E rightRes = query(rightIdx, mid+1, r, mid+1, queryR);
E merge = merger.merge(leftRes, rightRes);
return merge;
}
public void set(int idx,E e){
if (idx<0 || idx>=data.length) {
throw new IllegalArgumentException("index is illegal");
}
data = e;
set(0,0,data.length-1,idx,e);
}
//在treeIdx中为根的线段树中更新index的值为e
public void set(int treeIdx,int l ,int r,int index,E e){
if (l==r){
tree = e;
}
int mid = (l+r)>>1;
int leftTreeIndex = leftChild(treeIdx);
int rightTreeIndex = rightChild(treeIdx);
if (index>=mid+1){
set(rightTreeIndex,mid+1,r,index,e);
}else {
set(leftTreeIndex,l,mid,index,e);
}
tree = merger.merge(tree,tree);
}
private void buildSegmentTree(int treeIndex, int l, int r){
if(l == r){
tree = data;
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 = merger.merge(tree, tree);
}
public int getSize(){
return data.length;
}
public E get(int idx){
if (idx<0 || idx>=data.length){
throw new IllegalArgumentException("idx is illegal");
}
return data;
}
private int leftChild(int idx){
return 2*idx+1;
}
private int rightChild(int idx){
return 2*idx+2;
}
@Override
public String toString(){
StringBuilder sb= new StringBuilder();
sb.append('[');
for (int i = 0; i < tree.length; i++) {
if (tree!=null) {
sb.append(tree);
}else {
sb.append("null");
}
if (i!=tree.length-1){
sb.append(",");
}
}
sb.append(']');
return sb.toString();
}
}
Main方法测试类
public class Main {
public static void main(String[] args) {
Integer[] nums = {-2,0,3,-5,2,-1};
SegmentTree<Integer> segTree = new SegmentTree<>(nums,
(a, b) -> a + b);
System.out.println(segTree.query(0, 2));
System.out.println(segTree.query(2, 5));
System.out.println(segTree.query(0, 5));
}
}
Merger合并接口
public interface Merger<E> {
E merge(E a, E b);
}
@alittlebear 进来学习了{:301_978:}
感谢楼主分享，学习了！ 加油，一起学习
看不懂，但是勉强还是能运行的。。吧{:301_979:}
大佬好厉害 alittlebear 发表于 2020-11-30 01:16
看不懂，但是勉强还是能运行的。。吧
大佬好厉害
我也是研究了两天，debug一步一步看结运行果，才搞明白的{:301_1005:} 这个是数组类型定义的线性表的合并方法吗 wzh202 发表于 2020-11-30 12:39
这个是数组类型定义的线性表的合并方法吗
线段树不是属于线性表哦 wzh202 发表于 2020-11-30 12:39
这个是数组类型定义的线性表的合并方法吗
我把合并去掉给你看下
class NumArray { int [] data;
int [] tree;
public NumArray(int[] nums) {
int n = nums.length;
if (nums.length>0){
data = new int;
for (int i = 0; i < n; i++) {
data = nums;
}
tree = new int;
buildTree(0,0,n-1);
}
}
private void buildTree(int treeIdx, int l, int r) {
if (l==r){
tree = data;
return;
}
int mid = (l+r)>>1;
int leftIdx = leftChild(treeIdx);
int rightIdx = rightChild(treeIdx);
buildTree(leftIdx,l,mid);
buildTree(rightIdx,mid+1,r);
tree = tree+tree;
}
private int rightChild(int treeIdx) {
return treeIdx*2 +2;
}
private int leftChild(int treeIdx) {
return treeIdx*2+1;
}
public void update(int i, int val) {
update(0,0,data.length-1,i,val);
}
private void update(int treeIdx ,int l, int r, int target, int val) {
if (l==r){
tree = val;
return;
}
int mid = (l+r)>>1;
int leftIdx = leftChild(treeIdx);
int rightIdx = rightChild(treeIdx);
if (target>=mid+1){
update(rightIdx, mid+1, r, target, val);
}else {
update(leftIdx, l, mid, target, val);
}
tree = tree+tree;
}
public int sumRange(int i, int j) {
return query(0, 0, data.length - 1, i, j);
}
private int query(int treeIdx, int l, int r, int queryL, int queryR) {
if (queryL < 0 || queryL >= data.length || queryR < 0 || queryR >= data.length || queryL > queryR) {
throw new IllegalArgumentException();
}
if (l==queryL && r==queryR){
return tree;
}
int mid = (l+r)>>1;
int leftTreeIndex = leftChild(treeIdx);
int rightTreeIndex = rightChild(treeIdx);
if (queryR<=mid){
return query(leftTreeIndex, l, mid, queryL, queryR);
} else if (queryL >= mid + 1) {
return query(rightTreeIndex, mid+1, r, queryL, queryR);
}
intleftRes = query(leftTreeIndex, l, mid, queryL, mid);
intrightRes = query(rightTreeIndex, mid+1, r, mid+1, queryR);
return leftRes + rightRes;
}
}
在新标签打开所有链接复制所有链接URL复制所有链接URL（反向）复制所有链接标题 + URL复制所有链接标题 + URL (MD)复制所有链接标题 + URL (BBS)复制所有链接标题 + URL (筛选)复制所有链接标题 + URL (设置复制格式)在新标签页打开所有图片链接在一个标签页显示所有图片链接
复选框 - 选中
复选框 - 取消
复选框 - 反选
单选框 - 选中
单选框 - 取消
特殊单选框 - 选中
页:
[1]