[SDS 알고리즘 특강 복습] 2042 구간 합 구하기 (인덱스트리)

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

 

 

인덱스트리만 암기하고 있으면 바로 풀리는 문제

자료형(long)과 diff가 아니라 변화할 값이 입력으로 주어지는 것에만 주의하면 된다.

 

인덱스 트리 알고리즘은 잘 작성했는데 코드가 잘 작동하지않아 당황했다. 자료형과 diif가 아니라 변화할값이 입력으로 주어지는 것에 주의하지 못했다.

약간 신경론적으로 인덱스트리 알고리즘을 잘 작성했는지에 신경을 집중하다 보니
위 간단한 포인트들을 놓치게 된 것 같다.

인덱스 트리 알고리즘 작성에 확신을 가질 정도로 암기해 익숙해져야 할 듯 하다.

 

<내 정답 코드>

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

public class Main {

    static int N, M, K;
    static long[] arr;
    static long[] tree;
    static long[] ans;

    public static void main(String[] args) throws IOException {
        BufferedReader  br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new long[N+1];
        tree = new long[N*4];
        ans = new long[K];
        for(int i=0; i<N; i++) {
            arr[i] = Long.parseLong(br.readLine());
        }
        init(1, 0, N-1);
        int T = M+K;
        int k = 0;
        while(T-->0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());

            if (a == 1) {
                int b = Integer.parseInt(st.nextToken());
                long c = Long.parseLong(st.nextToken());
                update(1, 0, N-1, b-1, c-arr[b-1]);
                arr[b-1] = c;
            }
            else {
                long b = Long.parseLong(st.nextToken());
                long c = Long.parseLong(st.nextToken());
                sb.append(query(1, 0, N-1, b-1, c-1)+"\n");
            }
        }
        System.out.println(sb.toString());
    }
    static long init(int node, int start, int end) {
        if(start == end ) {
            tree[node] = arr[start];
            return tree[node];
        }
        int mid = (start+end) / 2;
        tree[node] = init(node*2, start, mid) + init(node*2+1, mid+1, end);
        return tree[node];
    }
    static long query(int node, int start, int end, long left, long right) {
        if(end < left || right < start ) return 0;
        if(left <= start && end <= right) return tree[node];
        int mid = (start + end) / 2;
        return query(node*2, start, mid, left, right) + query(node*2+1, mid+1, end, left, right);
    }
    static void update(int node, int start, int end, long idx, long diff) {
        if(end < idx || idx < start ) return;
        tree[node] += diff;
        if(start != end) {
            int mid = (start+end)/2;
            update(node*2, start, mid, idx, diff);
            update(node*2+1, mid+1, end, idx, diff);
        }
    }
}