RMQ問題の線分樹解法

3717 ワード
アルゴリズム String tree テーブル query クラス
RMQ(Range Minimum Query)問題は、入力数列A［0…n−1］の位置iから位置jまでの最小値を計算するRMQ［i,j］＝min｛A[k],k=i＋1…j｝です.RMQの解法は、Sparse Table(ST)アルゴリズムなどたくさんあります.RMQアルゴリズムは、特殊な＋1／−1 RMQに変換されたアルゴリズムであり、クエリの利便性のために、数列Aを前処理する必要があり、RMQアルゴリズムの前処理の複雑さとクエリの複雑さを、でそれぞれ表すと、線分ツリー(segment tree)でRMQ問題を解決する複雑さは、である.
線分樹解法は、まず線分樹(一本の二叉樹)を構築し、ルート結点対応区間0…n-1で、左右の子樹が下付き中間値で境界し、重複区間値がなく、葉結点が単値区間に対応します.線分樹根結点の高さが0なら、ツリー全体の高さはflook(look)を超えません.＋1は、完全に二叉の木のやり方によって、各結点をlevel orderによって一次元配列Mに預け入れ、配列Mの各要素値はこの結点に対応する区間［i…j］である.の最小値の下付き値k.完全な二叉樹のように要素間に空きがないことは保証できないが、下付き値2 k＋1と2 k＋2を利用して、ある結点kの左右の子供に素早くアクセスすることができます.検索には深さが必要です.したがって、複雑度はO(logn)です.Sparse Tableなどのアルゴリズムに比べて、検索の複雑度はO(1)より悪いです.
実装:
/**
 * 
 * Using Segment Tree to solve RMQ problem
 * time complexity: <O(n),O(logn)>
 * 
 * RMQ(A)-Range Minimum Query on array A: find the minimum value/index in the range A[i..j]
 *  
 * 
 * 
 *  
 * Copyright (c) 2011 ljs (http://blog.csdn.net/ljsspace/)
 * Licensed under GPL (http://www.opensource.org/licenses/gpl-license.php) 
 * 
 * @author ljs
 * 2011-08-02
 *
 */ 
public class RMQ_SegmentTree {	
	//return the heap-like array of the segment tree 
	//(Note: the segment tree is not a complete tree, but we
	//use an array to simulate a complete tree, so the array has some gaps)
	public int[] buildSegmentTree(int[] A){
		int n = A.length;
		int heapHeight = (int)(Math.log(n)/Math.log(2))+1;//h=floor(logN)+1; h starts with 0.
		int mSize = (1<<(heapHeight+1))-1; //total nodes = 2^(h+1)-1
		
		int[] M = new int[mSize];
		
		buildSegmentTree(M, 0, A, 0, n-1);
		return M;
	}
	
	private void buildSegmentTree(int[] M,int node,int[] A,int i,int j){		
		if(i==j){
			M[node] = i;
		}else{
			int leftnode=2*node+1;
			int rightnode=leftnode+1;
			
			buildSegmentTree(M,leftnode,A,i,(i+j)/2);
			buildSegmentTree(M,rightnode,A,(i+j)/2+1,j);
			
			if(A[M[leftnode]]<=A[M[rightnode]]){
				M[node] = M[leftnode];
			}else{
				M[node] = M[rightnode];
			}
		}
	}
	
	//x..y is the query interval of RMQ
	public int query(int[] M,int[] A,int x,int y){
		int n=A.length;
		return query(M,0,A,0,n-1,x,y);
	}
	
	//x..y is the query interval of RMQ
	//i..j is the current interval of a segment sub-tree's root
	private int query(int[] M,int node,int[] A,int i,int j,int x,int y){		
		//if the query interval doesn't intersect the current interval 
		//return -1
		if (x>j || y<i)
		    return -1;
		   
		//if the query interval entirely covers the current interval
		//return the current node's minimum index
		if(x<=i && y>=j){
			return M[node];
		}
		
		//split query interval
		int leftnode=2*node+1;
		int rightnode=leftnode+1;
		
		int mid = (i+j)/2;
		if(x>mid){
			//right branch
			return query(M,rightnode,A,mid+1,j,x,y);
		}else if(y<=mid){
			//left branch
			return query(M,leftnode,A,i,mid,x,y);
		}else{
			//mixed
			int p1 = query(M,leftnode,A,i,mid,x,y);
			int p2 = query(M,rightnode,A,mid+1,j,x,y);
			
			if(p1==-1)return p2;
			if(p2==-1)return p1;
			
			if(A[p1]<=A[p2])
				return p1;
			else
				return p2;
		}
	}

	public static void main(String[] args) {
		RMQ_SegmentTree rmqSegTree = new RMQ_SegmentTree();
	
		int[] A = new int[]{0,1,2,3,7,1,9,2,8,6};			
		int[] M = rmqSegTree.buildSegmentTree(A);
		
			
		//print RMQ table RMQ[i,j], each cell has the form: value/index
		System.out.println("RMQ table:");
		for(int x=0;x<A.length;x++){
			for(int y=0;y<x;y++){
				System.out.format("    ");
			}
			for(int y=x;y<A.length;y++){
				int p = rmqSegTree.query(M,A,x,y);				
				System.out.format(" %d/%d",A[p],p);
			}
			System.out.println();
		}		
	}

}
文字列類似度アルゴリズム(距離アルゴリズムの編集)
つのニュースのフロントエンドの試験問題は、主にアルゴリズムです.