BOJ. Coffe Shop (1275)

[Link] https://www.acmicpc.net/problem/1275

The array changes over time: each query asks for the sum from x through y, inclusive, and then assigns b to position a. An iterative segment tree stores each array value in a leaf and the sum of a node’s children in each internal node.

The tree uses a 2N array: leaf i is stored at index N + i (with zero-based i), and each parent is the sum of its children. This layout works for any N; it does not require padding to a power of two. To query an inclusive range, first order the endpoints and represent the range as the half-open interval [left, right). Move both bounds upward through the tree, adding the boundary node whenever it covers part of the remaining range. A point assignment replaces one leaf, then recomputes its ancestors.

Each query is answered before its assignment is applied, and that assignment is complete before the next query is read. The tree and all input values and sums use long so accumulated sums do not overflow int.

Building the tree takes O(N). Each of the Q queries performs one range sum and one point update, each in O(log N), for a total of O((N + Q) log N) time. The tree uses O(N) space.

Java

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

public class Main {
    static long[] tree;
    static int n;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(reader.readLine());
        n = Integer.parseInt(tokens.nextToken());
        int queryCount = Integer.parseInt(tokens.nextToken());

        tree = new long[2 * n];
        tokens = new StringTokenizer(reader.readLine());
        for (int i = 0; i < n; i++) {
            tree[n + i] = Long.parseLong(tokens.nextToken());
        }
        for (int node = n - 1; node > 0; node--) {
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }

        StringBuilder output = new StringBuilder();
        for (int i = 0; i < queryCount; i++) {
            tokens = new StringTokenizer(reader.readLine());
            int x = Integer.parseInt(tokens.nextToken());
            int y = Integer.parseInt(tokens.nextToken());
            int a = Integer.parseInt(tokens.nextToken()) - 1;
            long b = Long.parseLong(tokens.nextToken());

            int left = Math.min(x, y) - 1;
            int right = Math.max(x, y);
            output.append(rangeSum(left, right)).append('\n');
            assign(a, b);
        }
        System.out.print(output);
    }

    static long rangeSum(int left, int right) {
        long sum = 0;
        for (left += n, right += n; left < right; left /= 2, right /= 2) {
            if (left % 2 == 1) sum += tree[left++];
            if (right % 2 == 1) sum += tree[--right];
        }
        return sum;
    }

    static void assign(int position, long value) {
        int node = n + position;
        tree[node] = value;
        while (node > 1) {
            node /= 2;
            tree[node] = tree[node * 2] + tree[node * 2 + 1];
        }
    }
}