[자바, C++] 백준 11658 - 구간 합 구하기 3 (java cpp)

 문제 : boj11658

---

 

필요 알고리즘 개념

•  다차원 펜윅 트리, 세그먼트 트리 
  • 펜윅 트리 혹은 세그먼트 트리를 2차원에 대해 적용할 수 있어야 풀 수 있다.

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

 

---

 

풀이

  다차원 펜윅 트리, 세그먼트 트리 등으로 풀 수 있는 기본형태의 문제이다. 펜윅 트리로 풀려면 작성해둔 펜윅 트리 글에서 '응용 1' 부분을 읽어보면 이 문제를 풀 수 있다.

 

 

---

 

코드(C++) : github

#include <iostream>
#include <string.h>
using namespace std;

int N;
int arr[1025][1025];
int bit[1025][1025];

int getPrefixSum(int r, int c) {
    int sum = 0;
    while (r > 0) {
        int cc = c;
        while (cc > 0) {
            sum += bit[r][cc];
            cc -= cc&-cc;
        }
        r -= r&-r;
    }
    return sum;
}

void update(int r, int c, int diff) {
    while (r <= N) {
        int cc = c;
        while (cc <= N) {
            bit[r][cc] += diff;
            cc += cc&-cc;
        }
        r += r&-r;
    }
}

int query(int x1, int y1, int x2, int y2) {
    return getPrefixSum(x2, y2) - getPrefixSum(x2, y1-1) - getPrefixSum(x1-1,y2) + getPrefixSum(x1-1, y1-1);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    cin >> N >> m;
    memset(bit, 0, sizeof(bit));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            cin >> arr[i][j];
            update(i, j, arr[i][j]);
        }
    }

    int op, a, b, c, d, diff;
    while (m--) {
        cin >> op;
        if (op == 0) {
            cin >> a >> b >> c;
            diff = c - arr[a][b];
            arr[a][b] = c;
            update(a, b, diff);
        } else {
            cin >> a >> b >> c >> d;
            cout << query(a,b,c,d) << '\n';
        }
    }
    return 0;
}

 

 

코드(Java) : github

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

public class Main {
    int N;
    int[][] arr, bit;

    private int getPrefixSum(int r, int c) {
        int sum = 0;
        while (r > 0) {
            int cc = c;
            while (cc > 0) {
                sum += bit[r][cc];
                cc -= cc&-cc;
            }
            r -= r&-r;
        }
        return sum;
    }

    private void update(int r, int c, int diff) {
        while (r <= N) {
            int cc = c;
            while (cc <= N) {
                bit[r][cc] += diff;
                cc += cc&-cc;
            }
            r += r&-r;
        }
    }

    private void initBit() {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                update(i, j, arr[i][j]);
            }
        }
    }

    private int query(int x1, int y1, int x2, int y2) {
        return getPrefixSum(x2, y2) - getPrefixSum(x2, y1-1) - getPrefixSum(x1-1,y2) + getPrefixSum(x1-1, y1-1);
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        arr = new int[N+1][N+1];
        bit = new int[N+1][N+1];
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        initBit();

        StringBuilder sb = new StringBuilder();
        while (m-->0) {
            st = new StringTokenizer(br.readLine());
            switch (Integer.parseInt(st.nextToken())) {
                case 0:
                    int r = Integer.parseInt(st.nextToken());
                    int c = Integer.parseInt(st.nextToken());
                    int val = Integer.parseInt(st.nextToken());
                    int diff = val - arr[r][c];
                    arr[r][c] = val;
                    update(r, c, diff);
                    break;
                case 1:
                    int x1 = Integer.parseInt(st.nextToken());
                    int y1 = Integer.parseInt(st.nextToken());
                    int x2 = Integer.parseInt(st.nextToken());
                    int y2 = Integer.parseInt(st.nextToken());
                    sb.append(query(x1,y1,x2,y2)).append('\n');
            }
        }
        System.out.print(sb);
    }

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