BOJ. Minimum Value (10999)

Problem: BOJ 10999 — Range Sum 2 · 한국어 · 日本語

The array contains N values. An operation of type 1 adds D to every element in the inclusive, 1-indexed interval [B, C]; an operation of type 2 prints the sum over that same kind of interval. Both updates and queries must handle up to one million elements, and range sums can exceed 32-bit integer limits, so the tree and all arithmetic use long long.

The recursive segment tree stores the sum of each interval in tree[node] and the pending per-element addition in lazy[node]. apply(node, start, end, value) adds value * (end - start + 1) to the stored sum, because every element in that segment changes, and accumulates value in its lazy tag. Before descending into a partially covered node, push applies its tag to both children using their own segment lengths, then clears the parent’s tag. After recursively updating children, pull recomputes the parent sum from the two child sums. Fully covered nodes are handled with apply directly.

For a query, a fully covered node contributes its stored sum. Otherwise, push pending additions before descending and add the results from the intersecting children. Each operation visits only the segment-tree paths and their boundary siblings, so updates and queries each take O(log N) time. The tree and lazy-tag arrays use O(N) memory; recursive depth is O(log N), which is safe for N <= 1,000,000.

Input endpoints are 1-indexed and inclusive. The implementation converts them to 0-indexed endpoints; it does not need to turn the query into a half-open interval.

C++

#include <iostream>
#include <vector>
using namespace std;

using int64 = long long;

int n;
vector<int64> tree;
vector<int64> lazy;

void build(int node, int start, int end, const vector<int64>& values) {
    if (start == end) {
        tree[node] = values[start];
        return;
    }
    int mid = start + (end - start) / 2;
    build(node * 2, start, mid, values);
    build(node * 2 + 1, mid + 1, end, values);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

void apply(int node, int start, int end, int64 value) {
    tree[node] += value * (end - start + 1);
    lazy[node] += value;
}

void push(int node, int start, int end) {
    if (lazy[node] == 0 || start == end) return;

    int mid = start + (end - start) / 2;
    apply(node * 2, start, mid, lazy[node]);
    apply(node * 2 + 1, mid + 1, end, lazy[node]);
    lazy[node] = 0;
}

void update(int node, int start, int end, int left, int right, int64 value) {
    if (right < start || end < left) return;
    if (left <= start && end <= right) {
        apply(node, start, end, value);
        return;
    }

    push(node, start, end);
    int mid = start + (end - start) / 2;
    update(node * 2, start, mid, left, right, value);
    update(node * 2 + 1, mid + 1, end, left, right, value);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}

int64 query(int node, int start, int end, int left, int right) {
    if (right < start || end < left) return 0;
    if (left <= start && end <= right) return tree[node];

    push(node, start, end);
    int mid = start + (end - start) / 2;
    return query(node * 2, start, mid, left, right)
         + query(node * 2 + 1, mid + 1, end, left, right);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m, k;
    cin >> n >> m >> k;

    vector<int64> values(n);
    for (int i = 0; i < n; ++i) cin >> values[i];

    tree.assign(4 * n, 0);
    lazy.assign(4 * n, 0);
    build(1, 0, n - 1, values);

    for (int i = 0; i < m + k; ++i) {
        int type, b, c;
        cin >> type >> b >> c;
        --b;
        --c;

        if (type == 1) {
            int64 d;
            cin >> d;
            update(1, 0, n - 1, b, c, d);
        } else {
            cout << query(1, 0, n - 1, b, c) << '\n';
        }
    }
    return 0;
}