세그먼트트리.md

세그먼트트리로 구간합을 구하는 알고리즘이다.

https://www.acmicpc.net/problem/2042

import java.util.*;

public class boj2042{
    static Scanner sc = new Scanner(System.in);
    static long[] Tree;
    static long[] arr;
    
    static int log2(int x,int base){
        return (int) Math.ceil(Math.log10(x)/Math.log10(2));
    }
    
    /*
    makeTree :
    길이가 8인 배열이 있을때
    
                           (1-8의 구간합)
                          /              \
            (1-4의 구간합)               (5-4의 구간합)
           /             \              /             \
    (1-2의 구간합) (3-4의 구간합) (5-6의 구간합) (7-8의 구간합)
      /        \     /        \     /       \     /        \  
    (1)        (2) (3)        (4) (5)       (6) (7)        (8)
    
    재귀함수를 써서 이런 형태로 트리를 만든다. (Tree배열에 1차원으로 저장)
    (배열은 (1-8의 구간합), (1-4의 구간합), (5-4의 구간합), (1-2의 구간합), (3-4의 구간합), (5-6의 구간합)...의 순서로 구성)
    */
    
    static long makeTree(int l, int r, int x){
        if(l==r) Tree[x] = arr[l];
        else Tree[x] = makeTree(l,(l+r)/2,x*2)+makeTree((l+r)/2+1,r,x*2+1);
        return Tree[x];
    }

    /*
    updateTree :
    
                           (1-8의 구간합)
                         //              \
            (1-4의 구간합)               (5-4의 구간합)
           /            \\              /             \
    (1-2의 구간합) (3-4의 구간합) (5-6의 구간합) (7-8의 구간합)
      /        \     /       \\     /       \     /        \  
    (1)        (2) (3)        (4) (5)       (6) (7)        (8)
    
    4를 업데이트 한다고 가정,
    구간을 반으로 쪼개서 4가 왼쪽에 속하는지 오른쪽에 속하는지 판단해서 4가 구간에 포함된 노드를 탐색함
    그리고 4가 포함된 노드들의 바뀔 값-원래값을 더해줌
    */ 
    
    static void updateTree(int l, int r, int x, int goal, long val){
        Tree[x]+=val;
        if(l==r) return;
        if(l<=goal&&goal<=(l+r)/2) updateTree(l,(l+r)/2,x*2,goal,val);
        else if((l+r)/2+1<=goal&&goal<=r) updateTree((l+r)/2+1,r,x*2+1,goal,val);
    }

    /*
    sumTree :
    - 만약에 지금 위치가(지금 범위가) 내가 찾아야 하는 구간에 포함된다 -> 더해줌
    - 만약에 내가 합을 찾아야 하는 구간이 왼쪽의 부분집합이다 -> 왼쪽 탐색
    - 만약에 내가 합을 찾아야 하는 구간이 오른쪽의 부분집합이다 -> 오른쪽 탐색
    - 만약에 왼쪽이랑 오른쪽에 애매하게 겹쳐져있다 -> 왼쪽 오른쪽 쪼개서 탐색
    */
    
    static long sumTree(int l, int r, int x, int gl, long gr){
        if(gl<=l&&r<=gr)return Tree[x];
        else if(gr<=(l+r)/2) return sumTree(l,(l+r)/2,x*2,gl,gr);
        else if((l+r)/2+1<=gl) return sumTree((l+r)/2+1,r,x*2+1,gl,gr);
        else if(gl<=(l+r)/2&&(l+r)/2<=gr)return sumTree(l,(l+r)/2,x*2,gl,gr)+sumTree((l+r)/2+1,r,x*2+1,gl,gr);
        return 0;
    }
    
    public static void main(String[] args){
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        arr = new long[n];
        Tree = new long[(int)Math.pow(2,log2(n,2)+1)+1]; 
        
        for(int i = 0; i < n; i++)arr[i] = sc.nextLong();
        makeTree(0,n-1,1);
        
        for(int i = 0; i < m + k; i++){
            int c = sc.nextInt();
            int a = sc.nextInt();
            long b = sc.nextLong();
            
            if(c==1){
                long tmp = arr[a-1];
                arr[a-1] = b; 
                updateTree(0,n-1,1,a-1,b-tmp);
            } else if(c==2) {
                System.out.println(sumTree(0,n-1,1,a-1,b-1));
            }
        }
        sc.close();
    }
}