BOJ. Prefix sum (2042)

A Fenwick tree (binary indexed tree) stores partial sums so that a point update and a prefix-sum query each take O(log N) time. The input values are kept separately: when position i changes from old to new, add the difference new - old to the tree at the 1-based index i.

For a 1-based index i, i & -i extracts its lowest set bit. A prefix query repeatedly subtracts this value to move to the next disjoint block; an update repeatedly adds it to visit every containing block. The inclusive sum from a through b is prefix(b) - prefix(a - 1). Building the tree by propagating each initialized node to its parent takes O(N) time. Updates and queries take O(log N) time, and the value array plus tree use O(N) space. long stores both individual values and accumulated sums.

Problem link

Java

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();
        int updateCount = input.nextInt();
        int queryCount = input.nextInt();

        long[] values = new long[n];
        for (int i = 0; i < n; i++) {
            values[i] = input.nextLong();
        }
        FenwickTree tree = new FenwickTree(values);

        StringBuilder output = new StringBuilder();
        for (int i = 0; i < updateCount + queryCount; i++) {
            int type = input.nextInt();
            int a = input.nextInt();
            long b = input.nextLong();
            if (type == 1) {
                int index = a - 1;
                long delta = b - values[index];
                values[index] = b;
                tree.add(a, delta);
            } else {
                output.append(tree.prefixSum((int) b) - tree.prefixSum(a - 1)).append('\n');
            }
        }
        System.out.print(output);
    }

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

        FenwickTree(long[] values) {
            tree = new long[values.length + 1];
            for (int i = 1; i < tree.length; i++) {
                tree[i] += values[i - 1];
                int parent = i + (i & -i);
                if (parent < tree.length) {
                    tree[parent] += tree[i];
                }
            }
        }

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

        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++];
        }

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

            boolean negative = c == '-';
            if (negative) {
                c = read();
            }
            long value = 0;
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return negative ? -value : value;
        }

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