[Do It! 코딩테스트 자바편(김종관)] 문제 071(백준 2042번)

느낀점

• 교재 세그먼트 이론 부분이 자세히 설명해 놓아서, 이를 가지고 충실히 구현만 했더니 맞은 문제
• 내 풀이와 교재 풀이가 맥락은 똑같지만 조금씩 차이 나는 부분이 있으니, 다시 볼 때 둘 다 보면 좋을 것 같다.

문제

구간 합 구하기(백준: 2042번)

내 풀이

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

public class Main {
    static int nodeCnt, changeCnt, sumCnt;
    static long[] tree;
    static int powTwoK;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        nodeCnt = Integer.parseInt(st.nextToken());
        changeCnt = Integer.parseInt(st.nextToken());
        sumCnt = Integer.parseInt(st.nextToken());

        // 2^k 구하기
        powTwoK = 0;
        int exponent = 0;
        while (powTwoK < nodeCnt) {
            powTwoK = (int) Math.pow(2, exponent);
            exponent++;
        }

        // tree 초기화
        tree = new long[powTwoK * 2];
        // 인덱스 변경 -> 배열에 저장
        for (int i = powTwoK; i <= nodeCnt + powTwoK - 1; i++) {
            tree[i] = Long.parseLong(br.readLine());
        }
        // tree 나머지 채우기
        for (int i = powTwoK - 1;; i--) {
            if (i == 0)
                break;
            tree[i] = tree[2 * i] + tree[2 * i + 1];
        }

        for (int i = 1; i <= changeCnt + sumCnt; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            long c = Long.parseLong(st.nextToken());

            if (a == 1) {
                update(b, c);
            } else if (a == 2) {
                long res = getSum(b, (int) c);
                System.out.println(res);
            }
        }
    }

    private static long getSum(int s, int e) {
        s = s + powTwoK - 1;
        e = e + powTwoK - 1;

        long sum = 0;
        while (s <= e) {
            if (s % 2 == 1)
                sum += tree[s];
            if (e % 2 == 0)
                sum += tree[e];

            s = (s + 1) / 2;
            e = (e - 1) / 2;
        }
        return sum;
    }

    private static void update(int fromIdx, long to) {
        fromIdx = fromIdx + powTwoK - 1;
        long diff = to - tree[fromIdx];

        for (int i = fromIdx; i >= 1; i /= 2) {
            tree[i] = tree[i] + diff;
        }
    }
}

교재 풀이

import java.io.*;
import java.util.*;

public class MainTest {
  static long[] tree;

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken()); // 수의 개수
    int M = Integer.parseInt(st.nextToken()); // 변경이 일어나는 횟수
    int K = Integer.parseInt(st.nextToken()); // 구간 합을 구하는 횟수
    int treeHeight = 0;
    int lenght = N;
    while (lenght != 0) {
      lenght /= 2;
      treeHeight++;
    }
    int treeSize = (int) Math.pow(2, treeHeight + 1);
    int leftNodeStartIndex = treeSize / 2 - 1;
    tree = new long[treeSize + 1];
    // 데이터를 리프노드에 입력 받기
    for (int i = leftNodeStartIndex + 1; i <= leftNodeStartIndex + N; i++) {
      tree[i] = Long.parseLong(br.readLine());
    }
    setTree(treeSize - 1); // tree 만들기

    for (int i = 0; i < M + K; i++) {
      st = new StringTokenizer(br.readLine());
      long a = Integer.parseInt(st.nextToken());
      int s = Integer.parseInt(st.nextToken());
      long e = Long.parseLong(st.nextToken());

      if (a == 1) { // 변경
        changeVal(leftNodeStartIndex + s, e);
      } else if (a == 2) { // 구간 합
        s = s + leftNodeStartIndex;
        e = e + leftNodeStartIndex;
        System.out.println(getSum(s, (int) e));
      } else {
        return;
      }
    }

    br.close();
  }

  private static long getSum(int s, int e) {
    long partSum = 0;
    while (s <= e) {
      if (s % 2 == 1) {
        partSum = partSum + tree[s];
        s++;
      }
      if (e % 2 == 0) {
        partSum = partSum + tree[e];
        e--;
      }
      s = s / 2;
      e = e / 2;
    }
    return partSum;
  }

  private static void changeVal(int index, long val) {
    long diff = val - tree[index];
    while (index > 0) {
      tree[index] = tree[index] + diff;
      index = index / 2;
    }
  }

  private static void setTree(int i) {
    while (i != 1) {
      tree[i / 2] += tree[i];
      i--;
    }

  }

}