Sqrt Decomposition

평방분할 알고리즘

 

구간합을 구할때 쓰는 알고리즘이다. 구간을 √N 으로 나눠주고 그 구간의 합을 구하는 알고리즘이다.

 

만약 0~15 라면

크기가 4인 배열을 만든다음 0~3 , 4~7 , 8~11 ,12~15 합들을 배열에 넣어준다.

 

그리고 배열 4~7의 값을 구해라고하면 바로출력하면된다.

 

하지만 3~9처럼 걸쳐잇는 합을 출력해야할경우에는

left right를 만들어서 크기가 4식 나눳으므로 인덱스값이 4로나누엇을때 0이 되는애들이 될때가지 left를 더하거나 right를 빼면서 0이나오는 값으로 만들어준다. 안되는값들은 그냥 arr에서 직접 result에 더해준다.

 

package study;
 
public class sqrtDecomposition {
    static int N;
    static int bucket[];
    static int arr[]=     {1,2,3,4,5};
    static int sz=0;
    static void init() {
        //루트 N식 나눠서 합을 담는다.
        sz = (int) Math.sqrt(N);
        bucket = new int[(int)Math.sqrt(N)+1];
        for(int i=0;i<N;i++) {
            bucket[i/sz]+=arr[i];
        }
    }
    
    static long sum(int left,int right) {
        long result = 0;
        
        while(left%sz!=0&&left<=right) {
            result+=arr[left++];
        }
        
        while(right%sz!=0&&left<=right) {
            result+=arr[right--];
        }
        
        while(left<=right) {
            result+=bucket[left/sz];
            left+=sz;
        }
        
        return result;
    }
    
    static void update(int pos,int val) {
        int dif = val - arr[pos];
        arr[pos] =val;
        bucket[pos/sz]-=dif;
    }
    public static void main(String[] args) {
        N = 5;
        init();
        System.out.println(sum(0,4));
    }
}