문제

특정 구간에서 가장 작은 인덱스값을 구하는 문제다.
세그먼트 트리를 정확히 구현만 하면된다.
링크

세그먼트 트리

세그먼트 트리에서 헷갈리는것이 트리에 무엇을 저장하는가였다.

트리의 인덱스와 데이터의 인덱스를 구분해야 헷갈리지 않는다.
더 정확히 표현하면 각 트리 노드에 인덱스 범위를 저장되어있다고 생각하고 접근한다.(실제로 저장되는것은 인덱스 범위를 대표하는 값이다.)

예를 들어 data={11,10,9,8,7,6,0,5,4,3,2,1} 이고
트리는 data가 가장 작은 값을 갖는 인덱스를 저장한다면 트리에는 다음이 저장된다.

내가 너무 헷갈려서 그려봤다.
실제로 저장되는건 초록색값이고
분홍색은 각 node를 대표하는 data의 인덱스다.

아래의 그림은 트리의 각 노드가 대표하는 data의 인덱스만 표현한 것이다.
(출처 : 나동빈님 블로그)

예를 들어 데이터가 12개 (int[] data=new int[12] 한 형태) 가 있고

트리를 나타내는 graph(int[] graph=new int[PIV*2], PIV는 데이터 수 n을 넘어서는 2진수값, n이 10^6까지라면 PIV=(2<<20) 같이 표현 가능) 있을때

1번 노드 (graph[1])는 data[0]~data[11]를 대표하는 값이 들어있다. 이번처럼 가장 작은 값의 인덱스를 구하는 문제라면 가장 작은 인덱스가 들어가 있을것이다.
data={11,10,9,8,7,6,0,5,4,3,2,1} 라면 1번 노드에는 data[6]=0이므로 6이 들어가있을것이다.

세그먼트 트리는 2가지 연산이 존재한다.

• 구간값을 구하는 query
• 구간값을 변경하는 update

query

(출처 : 나동빈님 블로그)

만약에 인덱스 4번부터 8번까지 가장 작은 값(data값)을 갖는 인덱스가 무엇인지 묻는 쿼리가 온다면 1번 노드부터 탐색해 4~8를 포함하는 노드끼리만 비교하면 된다.

(상세 코드는 아래 참고)

update

(출처 : 나동빈님 블로그)

update도 비슷하게 1번 노드부터 내려가면서 내가 찾고싶은 index를 변경해주면 된다.
대신 index가 변경되었으니 해당 index를 포함하는 노드들도 같이 update를 해줘야한다.

나를 위한 꿀팁

query

나는 query를 다음처럼 쓴다.

// node : 노드의 인덱스(1부터 시작)
// s,e : 가능한 인덱스 범위, 위 예제에서는 0,11로하면 전체에서 찾는것임(트리를 내려갈수록 절반씩 줄어듦)
// l,r : 찾고자하는 범위, l,r 사이에 값을 구하고 싶을때 사용.(찾고자하는 기준이므로 변하지 않음)
private int query(int node,int s,int e,int l,int r) 

s,e를 줄여가며 l,r 사이에 값만 구하고싶은거다.
s,e와 l,r가 하나도 겹치지 않으면 반영하지 않을것이고
s,e가 정확히 l,r에 들어와있으면 해당 노드를 반환한다.

s,e과 l,r이 (l<s<r<e 나 s<l<e<r) 겹쳐잇다면
s,e를 절반으로 나눠 자식노드 둘을 더해준다.

update

// node : 노드의 인덱스
// s,e : 줄여나갈 범위 인덱스(query와 동일함)
// idx : 변경할 인덱스, idx가 s,e안에 포함되면 변경함.
// val : 변경할 값, 리프 노드에 저장할 값
private void update(int node,int s,int e,int idx,int val)

s,e를 줄여나가며 idx가 포함되는 node만 변경할 것이다.
리프노드(s==e)라면 해당 노드를 val로 변경할것이다.

변경했다면 변경한 자식노들도 재반영해줘야한다.

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class B14428_SOL{
    private static final int PIV=(1<<20);
    private static int n;
    private static int[] nums,graph=new int[2*PIV];
    public void input() throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stk;
        // n
        n=Integer.parseInt(br.readLine());
        nums=new int[n+1];
        // nums
        stk=new StringTokenizer(br.readLine());
        nums[0]=(1<<30);
        for(int i=1;i<n+1;i++){
            // init
            nums[i]=Integer.parseInt(stk.nextToken());
            update(1,1,n,i,i);
        }
        // query
        StringBuilder sb=new StringBuilder();
        int m=Integer.parseInt(br.readLine());
        while(m-->0){
            stk=new StringTokenizer(br.readLine());
            int c=Integer.parseInt(stk.nextToken());
            int a=Integer.parseInt(stk.nextToken());
            int b=Integer.parseInt(stk.nextToken());
            if(c==1){
                // update
                nums[a]=b;
                update(1,1,n,a,a);
            }
            else{
                sb.append(query(1,1,n,a,b)).append("\n");
            }
        }
        // print
        System.out.print(sb);
    }
    private void update(int node,int s,int e,int index,int val){
        // check
        if(s>index || index>e) return;
        if(s==e){graph[node]=val;return;}
        // update
        int mid=(s+e)/2;
        update(node*2,s,mid,index,val);
        update(node*2+1,mid+1,e,index,val);
        graph[node]=nums[graph[node*2]]>nums[graph[node*2+1]]
                ? graph[node*2+1]
                : graph[node*2];
    }
    private int query(int node,int s,int e,int l,int r){
        // check
        if(l>e || s>r) return 0;
        if(l<=s && e<=r) return graph[node];
        // query
        int mid=(s+e)/2;
        int leftNode=query(node*2,s,mid,l,r);
        int rightNode=query(node*2+1,mid+1,e,l,r);
        return nums[leftNode]>nums[rightNode]
                ? rightNode
                : leftNode;
    }
}
public class Main {
    public static void main(String[] args)throws IOException {
        B14428_SOL sol=new B14428_SOL();
        sol.input();
    }
}