BOJ. Array and Query (16975)

BOJ 16975: Array and Query

Range addition with a Fenwick difference tree

Keep the original values in a base array and represent later additions with a difference array. Adding x to every position in the 1-based inclusive range [left, right] changes only two difference entries: add x at left and -x at right + 1. Therefore, the prefix sum of the difference array at index i is exactly the total added to position i; its current value is base[i] + prefix(i).

A Fenwick tree stores those difference values. Each range update performs two Fenwick point updates, and each point query takes one prefix sum, so both operations take O(log N) time. The base array and Fenwick tree use O(N) space. The tree has an extra slot so an update ending at N can safely write the cancellation at N + 1; queries only sum through their requested index. Store values and additions as long so repeated accumulated additions do not overflow int.

import java.io.BufferedInputStream;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        long[] base = new long[n + 1];
        for (int i = 1; i <= n; i++) {
            base[i] = input.nextLong();
        }

        Fenwick difference = new Fenwick(n + 1);
        int queryCount = input.nextInt();
        StringBuilder output = new StringBuilder();
        for (int i = 0; i < queryCount; i++) {
            int type = input.nextInt();
            if (type == 1) {
                int left = input.nextInt();
                int right = input.nextInt();
                long amount = input.nextLong();
                difference.add(left, amount);
                difference.add(right + 1, -amount);
            } else {
                int index = input.nextInt();
                output.append(base[index] + difference.prefixSum(index)).append('\n');
            }
        }
        System.out.print(output);
    }

    private static final class Fenwick {
        private final long[] tree;

        Fenwick(int maximumIndex) {
            tree = new long[maximumIndex + 1];
        }

        void add(int index, long value) {
            for (int i = index; i < tree.length; i += i & -i) {
                tree[i] += value;
            }
        }

        long prefixSum(int index) {
            long sum = 0;
            for (int i = index; i > 0; i -= i & -i) {
                sum += tree[i];
            }
            return sum;
        }
    }

    private static final class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int length;
        private int position;

        private int read() throws IOException {
            if (position == length) {
                length = input.read(buffer);
                position = 0;
                if (length == -1) return -1;
            }
            return buffer[position++];
        }

        int nextInt() throws IOException {
            return (int) nextLong();
        }

        long nextLong() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }

            long value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value * sign;
        }
    }
}