[Java] 펜윈트리

Fenwick Tree는 Binary Indexed Tree라고도 하며, 줄여서 BIT라고 합니다.

동작방식

참고사이트에 자세한 동작 방식을 확인하여 주십시오.

시간복잡도

펜윅 트리는 대해 O(log n) 시간 복잡도를 가짐

참고사이트

https://www.acmicpc.net/blog/view/21

펜윅 트리 (바이너리 인덱스 트리)

기본코드

5 3 5 4 3 2 1 1 3 2 4 5 5

package segmenttree;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Fenwick {

    static int N;
    static int M;
    static int[] numbers;
    static int[][] questions;
    static int[] tree;

    public static void update(int x, int val) {
        for (int i=x; i<=N; i+=i&-i) {
            tree[i] += val;
        }
    }

    public static int query(int x) {
        int ans = 0;
        for (int i=x; i>0; i-=i&-i) {
            ans += tree[i];
        }
        return ans;
    }

    public static void main(String[] args) throws IOException {

        System.setIn(new FileInputStream("input\\rsq.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        numbers = new int[N+1];
        questions = new int[M][2];
        tree = new int[N+1];

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

        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            questions[i][0] = Integer.parseInt(st.nextToken());
            questions[i][1] = Integer.parseInt(st.nextToken());
        }

        br.close();

        for (int i=1; i<=N; i++) {
            update(i, numbers[i]);
        }

        for (int i=0; i<tree.length; i++) {
            System.out.println("tree[" + i + "] : " + tree[i]);
        }

        for (int i=0; i<M; i++) {
            bw.write((query(questions[i][1]) - query(questions[i][0]-1))+"\n");
        }

        bw.flush();
        bw.close();
    }
}