线段树详解分析
什么是线段树？
是用来存放给定区间（segment, or interval）内对应信息的一种数据结构。与树状数组（binary indexed tree）相似，线段树也用来处理数组相应的区间查询（range query）和元素更新（update）操作。与树状数组不同的是，线段树不止可以适用于区间求和的查询，也可以进行区间最大值，区间最小值（Range Minimum/Maximum Query problem）或者区间异或值的查询。
对应于树状数组，线段树进行更新（update）的操作为O(logn)，进行区间查询（range query）的操作也为O(logn)。
线段树是用一个完全二叉树来存储对应于其每一个区间（segment）的数据。该二叉树的每一个结点中保存着相对应于这一个区间的信息。同时，线段树所使用的这个二叉树是用一个数组保存的，与堆（Heap）的实现方式相同。
线段树的作用？
线段树可以使用log(n) 的时间复杂度来进行更新和查询数组范围的和。
构建线段树
线段树在初始化时可以创建4倍原数组大小的空间
static class SegmentTree {
int[] tree;
int N = 100;
public SegmentTree() {
tree = new int[N];
}
public void build_tree(int[] arr, int node, int start, int end) {
if (start == end) {
tree[node] = arr[start];
}else {
int mid = (start + end) / 2;
int left_node = node * 2 + 1;
int right_node = node * 2 + 2;
build_tree(arr, left_node, start, mid);
build_tree(arr, right_node, mid + 1, end);
tree[node] = tree[left_node] + tree[right_node];
}
}
public void update_tree(int[] arr, int node, int start, int end, int idx , int val){
if (start == end){
arr[idx] = val;
tree[node] = val;
return;
}
int mid = (start + end)/2;
int left_node = node * 2 + 1;
int right_node = node * 2 + 2;
if(idx <= mid) {
update_tree(arr, left_node, start, mid, idx, val);
}else {
update_tree(arr,right_node,mid+1,end,idx,val);
}
tree[node] = tree[left_node] + tree[right_node];
}
public int query_tree(int[] arr, int node, int start, int end,int L, int R){
if(L > end || R < start){
return 0;
}
else if(L <= start && R >= end){
return tree[node];
}
else if(start == end){
return tree[node];
}
int mid = (start + end)/2;
int left_node = node * 2 + 1;
int right_node = node * 2 + 2;
int left_sum = query_tree(arr,left_node,start,mid,L,R);
int right_sum = query_tree(arr,right_node,mid+1,end,L,R);
return left_sum + right_sum;
}
public void print(){
for (int i =0;i<15;i++){
System.out.println(tree[i]);
}
}
}eg
307. 区域和检索 - 数组可修改
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。
示例:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9 update(1, 2) sumRange(0, 2) -> 8
class NumArray {
int[] tree;
int[] arr;
public NumArray(int[] nums) {
tree = new int[nums.length * 4 + 1];
this.arr = nums;
if(nums != null && nums.length != 0){
build_tree(0,0,nums.length-1);
}
}
public void build_tree(int node, int start, int end){
if(start == end){
tree[node] = arr[start];
return;
}
int mid = (start + end) / 2;
int left_node = node * 2 + 1;
int right_node = node * 2 + 2;
build_tree(left_node,start,mid);
build_tree(right_node,mid+1,end);
tree[node] = tree[left_node] + tree[right_node];
}
public void update(int i, int val) {
update_tree(0,0,arr.length-1,i,val);
}
public void update_tree(int node,int start,int end, int i, int val){
if(start == end){
tree[node] = val;
arr[i] = val;
return;
}
int mid = (start + end)/2;
int left_node = node * 2 + 1;
int right_node = node * 2 + 2;
if(i <= mid){
update_tree(left_node,start,mid,i,val);
}else{
update_tree(right_node,mid+1,end,i,val);
}
tree[node] = tree[left_node] + tree[right_node];
}
public int sumRange(int i, int j) {
return query_tree(0,0,arr.length-1,i,j);
}
public int query_tree(int node, int start, int end, int L, int R){
if(R < start || L > end){
return 0;
}
else if(L >= start && R <= end){
return tree[node];
}else if(start == end){
return tree[node];
}
int mid = (start + end)/2;
int left_node = node * 2 + 1;
int right_node = node * 2 + 2;
int left_sum = query_tree(left_node,start,mid,L,R);
int right_sum = query_tree(right_node,mid+1,end,L,R);
return left_sum + right_sum;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录