[백준 16975번] [Lazy propagation / 세그먼트 트리] 수열과 쿼리 21

Approach

일반적인 세그 유형과는 살짝 차이가 있다.

잘 생각해보면 쿼리를 지속적으로 처리해야한다는 점에서 세그먼트 트리 자료구조를 활용하는 것이 유리하다고 판단하는 것까지는 쉽게 생각할 수 있다.

 

하지만, 일반적인 쿼리 문제와 달리 특정 index에 대한 값을 업데이트하고 구간에 대한 정보를 묻는 것이 아니라

구간에 대한 정보를 업데이트하고, 특정 index에 대한 정보를 묻는다는 점에서 차이가 존재한다.

 

잘 생각해보면, 세그먼트 트리의 하나의 노드에서 구간에 대한 정보를 가지고 있으므로 정확히 특정 구간이 원하는 구간 안에 정확이 들어왔을 경우에만 업데이트해주면 된다. 특정 index에 대한 정보는 해당 구간 index를 포함하고 있는 모든 노드값들에 대해 값을 더해주면 된다.

Code

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;

int move_x[4] = {-1, 1, 0, 0};
int move_y[4] = {0, 0, -1, 1};

ll seg[400000];

void init(int node, int start, int end, int index, ll value){
    if(index < start || end < index) return;
    if(start == end){
        seg[node] += value;
        return;
    }
    int mid = (start + end) >> 1;
    init(node * 2, start, mid, index, value);
    init(node * 2 + 1, mid + 1, end, index, value);
}
void update(int node, int start, int end, int left, int right, ll value){
    if(right < start || end < left) return;
    if(left <= start && end <= right){
        seg[node] += value;
        return;
    }
    int mid = (start + end) >> 1;
    update(node * 2, start, mid, left, right, value);
    update(node * 2 + 1, mid + 1, end, left, right, value);
}

ll query(int node, int start, int end, int index){
    if(index < start || end < index) return 0;
    if(start == end) return seg[node];
    int mid = (start + end) >> 1;
    return seg[node] + query(node * 2, start, mid, index) + query(node * 2 + 1, mid + 1, end, index);
}

int main() {
    fastio;
    memset(seg, 0, sizeof(seg));
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        int t;
        cin >> t;
        init(1, 1, 100000, i, t);
    }

    int m;
    cin >> m;
    for(int i = 0; i < m; i++){
        int t;
        cin >> t;
        if(t == 1){
            ll a, b, c;
            cin >> a >> b >> c;
            update(1, 1, 100000, a, b, c);
        }
        else{
            ll a;
            cin >> a;
            cout << query(1, 1, 100000, a) << "\n";
        }
    }
    return 0;
}