BOJ. Sum of numbers 7 (2268)

Problem: BOJ 2268 — Sum of numbers 7 · 한국어 · 日本語

The array has N elements, all initially zero. A command 0 a b prints the sum on the inclusive, 1-indexed interval from min(a, b) through max(a, b). A command 1 a b assigns b to element a; it replaces that element’s previous value. Update values are nonnegative in the problem, but may be zero. The sum can exceed a 32-bit integer, so the tree stores long long.

The iterative segment tree stores element i at tree[N + i], using zero-based i, and stores each internal node’s sum in its parent. The tree starts filled with zero, which directly represents the initially zero array. To assign a value, replace the corresponding leaf and recompute its ancestors up to the root; this takes O(log N).

For a sum command, first order the input endpoints so a <= b. Convert the inclusive 1-indexed interval [a, b] to the zero-indexed half-open interval [a - 1, b), then add N to both endpoints to obtain leaf indices. While left < right, an odd left endpoint denotes a complete node on the right boundary, so add tree[left] and advance it. An odd right endpoint means the node immediately before it belongs to the interval, so retreat it and add tree[right]. Move both endpoints to their parents and repeat. The half-open boundary makes single-element and reversed-input ranges work without special cases beyond ordering the endpoints. Each assignment and sum takes O(log N) time; the 2N-entry tree uses O(N) memory.

C++

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

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

    int n, m;
    cin >> n >> m;
    vector<long long> tree(2 * n, 0);

    while (m--) {
        int type, a;
        long long b;
        cin >> type >> a >> b;

        if (type == 1) {
            int position = n + a - 1;
            tree[position] = b;
            for (position >>= 1; position > 0; position >>= 1) {
                tree[position] = tree[position << 1] + tree[position << 1 | 1];
            }
        } else {
            int left = min(a, static_cast<int>(b)) - 1 + n;
            int right = max(a, static_cast<int>(b)) + n;
            long long sum = 0;

            while (left < right) {
                if (left & 1) {
                    sum += tree[left++];
                }
                if (right & 1) {
                    sum += tree[--right];
                }
                left >>= 1;
                right >>= 1;
            }
            cout << sum << '\n';
        }
    }
    return 0;
}