© 2025 anveloper.dev
GitHub·LinkedIn·Contact

목차

  • 문제
  • 입력
  • 출력
  • 예제
  • 풀이
  • 코드
  • 복잡도
풀이 목록으로 돌아가기

BOJ 2268 - 수들의 합 7

2023-01-01
BOJ
골드 I
java
원본 문제 보기
세그먼트 트리
자료 구조

문제

BOJ 2268 - 수들의 합 7

N개의 수가 있을 때, 다음 두 종류의 쿼리를 처리하는 프로그램을 작성하시오.

  • 쿼리 0: 0 i j — i번째 수부터 j번째 수까지의 합을 출력한다. i가 j보다 클 수도 있다.
  • 쿼리 1: 1 i j — i번째 수를 j로 바꾼다.

입력

첫째 줄에 N과 M이 주어진다. 이후 M개의 줄에 쿼리가 주어진다. 초기 수열의 모든 수는 0이다.

  • 1 ≤ N ≤ 1,000,000
  • 1 ≤ M ≤ 1,000,000

출력

쿼리 0에 대한 결과를 한 줄에 하나씩 출력한다.

예제

입력:

7 6
1 3 5
1 5 3
0 3 5
0 5 3
1 4 0
0 3 5

출력:

8
8
5

풀이

핵심 아이디어: **Fenwick Tree(BIT, Binary Indexed Tree)**를 사용하여 구간 합 쿼리와 점 업데이트를 모두 O(log N)에 처리한다. N과 M이 최대 100만이므로 일반 세그먼트 트리도 가능하지만, BIT가 구현이 간결하고 상수 계수가 작아 더 효율적이다.

  1. sum(pos): pos 이하 인덱스들의 합을 반환한다. pos & (pos - 1)을 이용해 낮은 비트를 제거하며 누적한다.
  2. add(pos, val): pos 위치에 val을 더한다. pos += (pos & -pos)를 이용해 영향 받는 모든 노드를 갱신한다.
  3. 구간 합 [i, j]: sum(j) - sum(i-1)로 계산한다. i가 j보다 크면 자동으로 교환하여 처리한다.
  4. 업데이트: 현재 값 arr[i]를 기억해두고 add(i, j - arr[i])로 차이만큼 업데이트한다.
  5. 빠른 입력: N, M이 100만이므로 BufferedReader보다 빠른 커스텀 InputReader를 사용한다.

코드

package day349;
 
import java.io.*;
import java.util.*;
 
public class Day328BOJ2268수들의합 { // goo선생님
    static int num, numOfQueries;
    static long[] tree, arr;
 
    static long sum(int pos) {
        long ret = 0;
        while (pos > 0) {
            ret += tree[pos];
            pos &= (pos - 1);
        }
        return ret;
    }
 
    static void add(int pos, long val) {
        while (pos < tree.length) {
            tree[pos] += val;
            pos += (pos & -pos);
        }
    }
 
    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader(System.in);
        StringBuilder sb = new StringBuilder();
        num = in.nextInt();
        numOfQueries = in.nextInt();
        tree = new long[num + 1];
        arr = new long[num + 1];
        for (int idx = 0; idx < numOfQueries; idx++) {
            int type = in.nextInt();
            int i = in.nextInt();
            int j = in.nextInt();
            long val;
            if (type == 0) {
                if (i <= j)
                    val = sum(j) - sum(i - 1);
                else
                    val = sum(i) - sum(j - 1);
                sb.append(val).append("\n");
            } else {
                add(i, j - arr[i]);
                arr[i] = j;
            }
        }
        System.out.println(sb);
    }
 
    static class InputReader {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
 
        public InputReader(InputStream st) {
            this.stream = st;
        }
 
        public int read() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int nextInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
    }
}

복잡도

  • 시간: O(M log N) — 쿼리 M개, 각각 O(log N)
  • 공간: O(N) — Fenwick Tree 배열