這兩天做題遇到求疊加矩形的面積,需要利用到線段樹,然后學(xué)習(xí)了下.
遇到兩種使用場景,先記錄下來,以后有時間再更深入了解下;
總體感悟: 線段樹解決問題像是dp思想的一種延伸,用更高效的數(shù)據(jù)結(jié)構(gòu)存儲中間結(jié)果,便于更新和查詢;
情況一:
區(qū)間更新,區(qū)間查詢
題: #### 850. 矩形面積 II
/**
* 采用從底向上線性掃描;
* 線性掃描+離散化+線段樹(帶lazy)
**/
class Solution {
public int[][] Tree;
// 標(biāo)示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 ,先全扔在葉子節(jié)點上(全扔子節(jié)點又感覺浪費線段樹了)
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坐標(biāo)個數(shù)();
HashSet<Integer> X = new HashSet<Integer>();
for(int[] arr:rectangles){
// 底邊-0:底邊左端點x坐標(biāo),1:底邊右端點坐標(biāo),2:底邊高度,3:標(biāo)識底邊還是頂邊
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++;
}
// 構(gòu)建線段樹(這里暫時決定用數(shù)組表示樹形結(jié)構(gòu)),一共是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坐標(biāo),1:底邊右端點坐標(biāo),2:底邊高度,3:標(biāo)識底邊還是頂邊
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));
}
}
情況二:
單點更新,區(qū)間查詢:
題: 求最長遞增子序列的個數(shù);
這題也可以動態(tài)規(guī)劃求,但是每次求dp[i]需要把dp[0]到dp[i-1]都更新一遍;
用線段樹思想是不斷的更新一張表,該表的每一項記錄以某個值結(jié)尾的最長子序列的長度以及數(shù)量;
class Solution {
// 核心思想:建立一個數(shù)組,維護(hù)從最小到最大值的線段樹,每一段節(jié)點值包含長度和數(shù)量---表征現(xiàn)有序列中以x為最長子序列尾部數(shù)字時,最長子序列的長度和數(shù)量;(該題利用了線段樹快速范圍查詢和單點修改的特性)
// Tree[x][0]標(biāo)示從0到p(l,r)范圍內(nèi)為子序列結(jié)尾的最長子序列長度len,Tree[x][1]標(biāo)示最長子序列數(shù)量count
public int[][] Tree;
public void build(int p,int left,int right){
// 這里情況特殊不需要像一般線段樹那樣進(jìn)行遞歸初始化;
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};
}
// 區(qū)間查詢 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);
// 左右長度一致的時候返回,該長度的數(shù)量為左右之和,否則為長的那個;
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;
// 對出現(xiàn)的數(shù)字進(jìn)行離散化;(如果范圍限定的小,數(shù)字比較均勻可以不需要離散化)
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();
// 建立離散化后數(shù)值與腳標(biāo)的索引;
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];
}
}
