BOJ. Prefix Product (11505)

Problem

Maintain an array under point assignments and answer the product of any inclusive range modulo 1,000,000,007. Since an update changes only one position, an iterative segment tree can recompute just the ancestors of that leaf. Each internal node stores the product of its two children modulo MOD.

The tree uses n leaves at indices [n, 2n). To assign index p, replace leaf p + n, then walk upward and recompute each parent. For a query [left, right], convert it to the half-open interval [left + n, right + n + 1). At each level, consume a left boundary node when it is a right child and a right boundary node when it is a left child; then move both boundaries to their parents. This visits only the canonical tree nodes covering the requested interval, including either endpoint exactly once.

Multiplication modulo MOD has identity 1, so both query accumulators start at 1; this also makes the result of a single-element range and ranges containing zero correct. Assignments store the new value directly, including 0—there is no division or special zero bookkeeping. Cast one factor to long before multiplying, since two values below MOD can overflow a 32-bit integer. The tree is built in O(N) time, each point assignment and range query takes O(log N), and the tree uses O(N) space.

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

public class Main {
    private static final int MOD = 1_000_000_007;

    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        int updates = input.nextInt();
        int queries = input.nextInt();
        int operationCount = updates + queries;

        int[] tree = new int[2 * n];
        for (int i = 0; i < n; i++) {
            tree[n + i] = input.nextInt();
        }
        for (int node = n - 1; node > 0; node--) {
            tree[node] = multiply(tree[node << 1], tree[node << 1 | 1]);
        }

        StringBuilder output = new StringBuilder();
        for (int i = 0; i < operationCount; i++) {
            int type = input.nextInt();
            int b = input.nextInt();
            int c = input.nextInt();
            if (type == 1) {
                set(tree, n, b - 1, c);
            } else {
                output.append(product(tree, n, b - 1, c)).append('\n');
            }
        }
        System.out.print(output);
    }

    private static int multiply(int a, int b) {
        return (int) ((long) a * b % MOD);
    }

    private static void set(int[] tree, int n, int index, int value) {
        int node = n + index;
        tree[node] = value;
        while ((node >>= 1) > 0) {
            tree[node] = multiply(tree[node << 1], tree[node << 1 | 1]);
        }
    }

    // Returns the product on the zero-based inclusive interval [left, right].
    private static int product(int[] tree, int n, int left, int right) {
        int l = left + n;
        int r = right + n + 1;
        int leftProduct = 1;
        int rightProduct = 1;
        while (l < r) {
            if ((l & 1) != 0) leftProduct = multiply(leftProduct, tree[l++]);
            if ((r & 1) != 0) rightProduct = multiply(tree[--r], rightProduct);
            l >>= 1;
            r >>= 1;
        }
        return multiply(leftProduct, rightProduct);
    }

    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 {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

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