백준[16975] 수열과 쿼리 21

문제 설명

문제 링크

http://icpc.me/15655

15655번: N과 M (6)

풀이 1

세그먼트 트리의 구간 업데이트를 하는 lazy propagation을 이용하여 풀이할 수 있다.

lazy propagation에 대한 자세한 설명은 여기와 여기를 참고해라.

풀이 2

lazy propogation을 사용하지 않고, 세그먼트 트리만을 이용하여 풀이할 수도 있다.

아래 그림과 같이 업데이트하는 방식과 쿼리를 리턴하는 방식을 기존과 반대로 하면 구간 업데이트에 대해 O(logN)에 처리할 수 있고, 한 점의 쿼리에 대해서도 O(logN)에 처리할 수 있다.

예시

코드 1

#include <cstdio>

using ll = long long;

ll arr[100005], tree[400005], lazy[400005];

ll init(ll node, ll s, ll e) {
    if (s == e) return tree[node] = arr[s];
    ll mid = (s + e) >> 1;
    return tree[node] = init(2 * node, s, mid) + init(2 * node + 1, mid + 1, e);
}

void propagate(ll node, ll s, ll e) {
    if (lazy[node]) {
        tree[node] += (e - s + 1) * lazy[node];
        if (s != e) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
    }
    lazy[node] = 0;
}

void update(ll node, ll s, ll e, ll qs, ll qe, ll add) {
    propagate(node, s, e);
    if (qe < s || e < qs) return;
    if (qs <= s && e <= qe) {
        tree[node] += (e - s + 1) * add;
        if (s != e) {
            lazy[2 * node] += add;
            lazy[2 * node + 1] += add;
        }
        return;
    }
    ll mid = (s + e) >> 1;
    update(2 * node, s, mid, qs, qe, add);
    update(2 * node + 1, mid + 1, e, qs, qe, add);
    tree[node] = tree[2 * node] + tree[2 * node + 1];
}

ll query(ll node, ll s, ll e, ll qs, ll qe) {
    propagate(node, s, e);
    if (qe < s || e < qs) return 0;
    if (qs <= s && e <= qe) return tree[node];
    ll mid = (s + e) >> 1;
    return query(2 * node, s, mid, qs, qe) + query(2 * node + 1, mid + 1, e, qs, qe);
}

int main() {
    ll n; scanf("%lld", &n);
    for (ll i = 0; i < n; i++) scanf("%lld", arr + i);
    init(1, 0, n - 1);

    ll q; scanf("%lld", &q);
    while (q--) {
        ll k; scanf("%lld", &k);
        if (k == 1) {
            ll a, b, c; scanf("%lld %lld %lld", &a, &b, &c);
            update(1, 0, n - 1, a - 1, b - 1, c);
        } else {
            ll a; scanf("%lld", &a);
            printf("%lld\n", query(1, 0, n - 1, a - 1, a - 1));
        }
    }
}

코드 2

#include <cstdio>

using ll = long long;

ll seg[400005], arr[100005];

void init(ll node, ll s, ll e) {
    if (s == e) {
        seg[node] = arr[s];
        return;
    }
    ll mid = (s + e) >> 1;
    init(2 * node, s, mid);
    init(2 * node + 1, mid + 1, e);
}

void update(ll node, ll s, ll e, ll qs, ll qe, ll num) {
    if (e < qs || qe < s) return;
    if (qs <= s && e <= qe) {
        seg[node] += num;
        return;
    }
    ll mid = (s + e) >> 1;
    update(2 * node, s, mid, qs, qe, num);
    update(2 * node + 1, mid + 1, e, qs, qe, num);
}

ll query(ll node, ll s, ll e, ll idx, ll ans) {
    if (e < idx || idx < s) return 0;
    ans += seg[node];
    if (s == e) return ans;
    ll mid = (s + e) >> 1; 
    return query(2 * node, s, mid, idx, ans) + query(2 * node + 1, mid + 1, e, idx, ans) ;
}

int main() {
    ll n; scanf("%lld", &n);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", arr + i);
    }
    init(1, 0, 1e5);
    ll m; scanf("%lld", &m);
    while (m--) {
        ll c; scanf("%lld", &c);
        if (c == 1) {
            ll qs, qe, num; scanf("%lld %lld %lld", &qs, &qe, &num);
            update(1, 0, 1e5, qs, qe, num);
        } else {
            ll idx; scanf("%lld", &idx);
            printf("%lld\n", query(1, 0, 1e5, idx, 0));
        }
    }    
}