BOJ 16975 수열과 쿼리 21

1 개요

BOJ 16975 수열과 쿼리 21

• 백준 온라인 저지 16975번 문제
• BOJ 45단계

2 C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

struct SegmentTree {
    int n;
    vector<ll> tree, lazy;

    SegmentTree(const vector<int>& arr) {
        n = arr.size();
        tree.resize(4 * n);
        lazy.resize(4 * n);
        build(arr, 1, 0, n - 1);
    }

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

    void propagate(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += (end - start + 1) * lazy[node];
            if (start != end) {
                lazy[node * 2] += lazy[node];
                lazy[node * 2 + 1] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    void updateRange(int node, int start, int end, int l, int r, int val) {
        propagate(node, start, end);
        if (start > end || start > r || end < l)
            return;
        if (start >= l && end <= r) {
            tree[node] += (end - start + 1) * val;
            if (start != end) {
                lazy[node * 2] += val;
                lazy[node * 2 + 1] += val;
            }
            return;
        }
        int mid = (start + end) / 2;
        updateRange(node * 2, start, mid, l, r, val);
        updateRange(node * 2 + 1, mid + 1, end, l, r, val);
        tree[node] = tree[node * 2] + tree[node * 2 + 1];
    }

    ll query(int node, int start, int end, int idx) {
        propagate(node, start, end);
        if (start == end) {
            return tree[node];
        }
        int mid = (start + end) / 2;
        if (idx <= mid)
            return query(node * 2, start, mid, idx);
        else
            return query(node * 2 + 1, mid + 1, end, idx);
    }

    void updateRange(int l, int r, int val) {
        updateRange(1, 0, n - 1, l, r, val);
    }

    ll query(int idx) {
        return query(1, 0, n - 1, idx);
    }
};

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

    int N, M, command, i, j, k, x;
    cin >> N;
    vector<int> arr(N);
    for (int& a : arr) cin >> a;

    SegmentTree st(arr);
    cin >> M;
    while (M--) {
        cin >> command;
        if (command == 1) {
            cin >> i >> j >> k;
            st.updateRange(i - 1, j - 1, k);
        } else {
            cin >> x;
            cout << st.query(x - 1) << '\n';
        }
    }
}