这两天做题遇到求叠加矩形的面积,需要利用到线段树,然后学习了下.
遇到两种使用场景,先记录下来,以后有时间再更深入了解下;
总体感悟: 线段树解决问题像是dp思想的一种延伸,用更高效的数据结构存储中间结果,便于更新和查询;
情况一:
区间更新,区间查询
题: #### 850. 矩形面积 II
/**
* 采用从底向上线性扫描;
* 线性扫描+离散化+线段树(带lazy)
**/
class Solution {
public int[][] Tree;
// 标示l到r+1点之间范围
public void build(ArrayList<Integer> xValue,int p,int l,int r){
if(l==r){
Tree[p]= new int[]{0,xValue.get(r+1)-xValue.get(l)};
return;
}
int mid = (l+r)/2;
build(xValue,2*p,l,mid);
build(xValue,2*p+1,mid+1,r);
Tree[p]=new int[]{0,xValue.get(r+1)-xValue.get(l)};
}
// 由于有加有减,暂时没想好怎么处理cover ,先全扔在叶子节点上(全扔子节点又感觉浪费线段树了)
public void add(int p,int l,int r,int x1,int x2,int cover){
//if(x1<=l&&x2>=r&&l==r){ // 提高效率的话去掉ll==rr,想办法
if(x1<=l&&x2>=r){ // 提高效率的话去掉ll==rr,想办法
Tree[p][0]+=cover;
return;
}
int mid= (l+r)/2;
if(x1>mid){
add(2*p+1,mid+1,r,x1,x2,cover);
return;
}
if(x2<=mid){
add(2*p,l,mid,x1,x2,cover);
return;
}
add(2*p,l,mid,x1,mid,cover);
add(2*p+1,mid+1,r,mid+1,x2,cover);
}
public int query(int p, int l, int r, int x1, int x2){
if(x1>x2) return 0;
//if(x1<=l&&x2>=r&&l==r){
if(x1<=l&&x2>=r){
if(Tree[p][0]<0) return 0;
if(Tree[p][0]>0) return Tree[p][1];
if(l==r&&Tree[p][0]==0) return 0;
}
int mid=(l+r)/2;
if(x1>mid) return query(2*p+1,mid+1,r,x1,x2);
if(x2<=mid) return query(2*p,l,mid,x1,x2);
return query(2*p,l,mid,x1,mid)+query(2*p+1,mid+1,r,mid+1,x2);
}
public int rectangleArea(int[][] rectangles) {
// 用来存储由底往上的扫描线
ArrayList<int[]> lines = new ArrayList<int[]>();
// 存储所有x坐标个数();
HashSet<Integer> X = new HashSet<Integer>();
for(int[] arr:rectangles){
// 底边-0:底边左端点x坐标,1:底边右端点坐标,2:底边高度,3:标识底边还是顶边
int[] upLine = new int[]{arr[0],arr[2],arr[1],1};
int[] downLine = new int[]{arr[0],arr[2],arr[3],-1};
lines.add(upLine);
lines.add(downLine);
X.add(arr[0]);
X.add(arr[2]);
}
// 按照底边的高度从低到高排序;
lines.sort((int[] o1,int[] o2)->{
return o1[2]-o2[2];
});
// 离散化
ArrayList<Integer> xValue = new ArrayList<Integer>(X);
xValue.sort((Integer o1,Integer o2)->{ return o1-o2;});
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
int index = 0;
for(int x:xValue){
map.put(x,index);
index++;
}
// 构建线段树(这里暂时决定用数组表示树形结构),一共是map.size()-1段, 0-左index,1-右index,2:cover,3-sum;
int size = map.size()-1;
Tree = new int[4*size][2];
// 初始化空Tree;
build(xValue,1,0,size-1);
long sum = 0;
int pre = 0;
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
// 底边-0:底边左端点x坐标,1:底边右端点坐标,2:底边高度,3:标识底边还是顶边
for(int[] line:lines){
if(line[2]==pre){
int ll = map.get(line[0]);
int rr = map.get(line[1])-1;
add(1,0,size-1,ll,rr,line[3]);
min=Math.min(ll,min);
max=Math.max(rr,max);
continue;
}else if(line[2]>pre){
int len = query(1,0,size-1,min,max);
int height = line[2]-pre;
sum+=(long)len*(long)height;
sum=sum%((long)Math.pow(10,9)+7);
pre = line[2];
int ll = map.get(line[0]);
int rr = map.get(line[1])-1;
add(1,0,size-1,ll,rr,line[3]);
min=Math.min(ll,min);
max=Math.max(rr,max);
}
}
return (int)(sum%((long)Math.pow(10,9)+7));
}
}
情况二:
单点更新,区间查询:
题: 求最长递增子序列的个数;
这题也可以动态规划求,但是每次求dp[i]需要把dp[0]到dp[i-1]都更新一遍;
用线段树思想是不断的更新一张表,该表的每一项记录以某个值结尾的最长子序列的长度以及数量;
class Solution {
// 核心思想:建立一个数组,维护从最小到最大值的线段树,每一段节点值包含长度和数量---表征现有序列中以x为最长子序列尾部数字时,最长子序列的长度和数量;(该题利用了线段树快速范围查询和单点修改的特性)
// Tree[x][0]标示从0到p(l,r)范围内为子序列结尾的最长子序列长度len,Tree[x][1]标示最长子序列数量count
public int[][] Tree;
public void build(int p,int left,int right){
// 这里情况特殊不需要像一般线段树那样进行递归初始化;
for(int i=1;i<Tree.length;i++){
Tree[i][1]=1;
}
// if(left>right) return;
// if(left==right){
// Tree[p][0]=0;
// Tree[p][1]=1;
// return;
// }
// int mid = (left+right)/2;
// build(2*p,left,mid);
// build(2*p+1,mid+1,right);
// Tree[p]=new int[]{0,1};
}
// 区间查询 0-left,0-left+1,...,0-right中最长的递增子序列
public int[] query(int p,int l,int r,int left,int right){
if(left>right) return new int[]{0,1};
if(left<=l&&right>=r) return Tree[p];
int mid = (l+r)/2;
if(left>mid){
return query(p<<1|1,mid+1,r,left,right);
}
if(right<=mid){
return query(p<<1,l,mid,left,right);
}
int[] lResult = query(p<<1,l,mid,left, mid);
int[] rResult = query(p<<1|1,mid+1,r,mid+1,right);
// 左右长度一致的时候返回,该长度的数量为左右之和,否则为长的那个;
if(lResult[0]==rResult[0]){
int len=lResult[0];
// 这里需要特殊考虑len=0时不要累加count
if(len==0) return new int[]{0,1};
int count=lResult[1]+rResult[1];
return new int[]{len,count};
}
return lResult[0]>rResult[0]?lResult:rResult;
}
// 单点修改,更新树;
public void update(int p,int l,int r,int index,int len,int count){
// 找到位置就修改;
if(l==r&&l==index){
if(Tree[p][0]==len){
Tree[p][1]+=count;
}else{
Tree[p][0]=len;
Tree[p][1]=count;
}
return;
}
int mid = (l+r)/2;
if(index>mid){
update(p<<1|1,mid+1,r,index,len,count);
}else{
update(p<<1,l,mid,index,len,count);
}
if(Tree[p<<1|1][0]==Tree[p<<1][0]){
Tree[p]=new int[]{Tree[p<<1][0],Tree[p<<1][1]+Tree[p<<1|1][1]};
return;
}
Tree[p]=Tree[p<<1][0]>Tree[p<<1|1][0]?Tree[p<<1]:Tree[p<<1|1];
}
public int findNumberOfLIS(int[] nums) {
if(nums==null||nums.length==0) return 0;
// 对出现的数字进行离散化;(如果范围限定的小,数字比较均匀可以不需要离散化)
HashSet<Integer> set = new HashSet<Integer>();
for(int i:nums){
set.add(i);
}
ArrayList<Integer> list = new ArrayList<Integer>(set);
list.sort((Integer o1,Integer o2)->{return o1-o2;});
int size = list.size();
// 建立离散化后数值与脚标的索引;
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0;i<size;i++){
map.put(list.get(i),i);
}
// 初始化线段树尺寸;
Tree = new int[size*4][2];
// 建立线段树
build(1,0,size-1);
// 单点更新线段树
for(int i:nums){
int index = map.get(i);
int[] val = query(1,0,size-1,0,index-1);
update(1,0,size-1,index,val[0]+1,val[1]);
}
return query(1,0,size-1,0, size-1)[1];
}
}
