[자바] 백준 18436 - 수열과 쿼리 37 (java)

목차

문제 : boj18436

 

 

필요 알고리즘

• 세그먼트 트리, 펜윅 트리, 제곱근 분할법
  
  • 위 알고리즘 혹은 자료구조 중 아무꺼나 쓰면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  세그먼트 트리, 펜윅 트리, 제곱근 분할법 등 풀 수 있는 방법은 많다. 아무튼 단일 업데이트, 범위 쿼리를 유효한 시간 내에 처리 가능한 코드를 짜면 된다. 이하 코드는 펜윅 트리를 사용해 풀었다. 펜윅트리에 대한 설명은 '이 글'에서 볼 수 있다.

 

 

코드 : github

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

public class Main {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1 << 16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        Bit[] bit = new Bit[2];
        bit[0] = new Bit(n);
        bit[1] = new Bit(n);

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) updateBothBit(bit, i, Integer.parseInt(st.nextToken()));

        int m = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            if (a == 1) updateBothBit(bit, b, c);
            else sb.append(bit[a-2].query(b, c)).append('\n');
        }

        System.out.print(sb);
    }

    private void updateBothBit(Bit[] bit, int ith, int value) {
        bit[0].update(ith, value%2==0?1:0);
        bit[1].update(ith, value%2==0?0:1);
    }
}

class Bit {
    private int[] bit, arr;
    private int n;

    Bit(int n) {
        this.n = n;
        bit = new int[n+1];
        arr = new int[n+1];
    }

    void update(int ith, int val) {
        int diff = val - arr[ith];
        if (diff == 0) return;

        arr[ith] = val;

        while (ith <= n) {
            bit[ith] += diff;
            ith += ith&-ith;
        }
    }

    int query(int b, int c) {
        return getPrefixSum(c) - getPrefixSum(b-1);
    }

    private int getPrefixSum(int ith) {
        int answer = 0;
        while (ith > 0) {
            answer += bit[ith];
            ith -= ith&-ith;
        }
        return answer;
    }
}