[C++] 16975번 수열과 쿼리 21 - 자료 구조, 세그먼트 트리, 느리게 갱신되는 세그먼트 트리

거의 똑같은 문제인 10999번 구간 합 구하기 2와 함께 풀이됩니다.

1. 문제

• 어떤 N개의 수가 있다. 중간에 어떤 구간에 특정 수를 더해주는 과정이 일어나고 그 중간에 어떤 부분의 합을 구하려 한다.

<입력>

• -1-   수의 개수 \(N(1 \leq N \leq 1,000,000)\)과 \(M(1 \leq M \leq 10,000)\), \(K(1 \leq K \leq 10,000)\)이 주어진다.
  • M은 수의 변경이 일어나는 횟수., K는 구간의 합을 구하는 횟수이다.
• -2~N+1-   N개의 수가 주어진다.
• -N+2~N+M+K+1-   세 개의 정수 a, b, c 또는 a, b, c, d가 주어진다. a가 1인 경우 b~c번째 수에 d를 더하고, a가 2인 경우 b~c번째 수의 합을 출력하라.
  • 입력으로 주어지는 모든 수는 \(-2^{63}\)보다 크고 \(2^{63}-1\)보다 작거나 같은 정수이다.

<출력>

• 구간의 합 S를 출력하라. \(S(-2^{63} \leq S \leq 2^{63}-1, S \in \mathbb{z})\)

2. 재정의

• 구간에 합하는 과정 동안에 구간의 합을 구하여라.

3. 해결 방법

• 느리게 갱신되는 세그먼트 트리를 사용한다.

4. 실수한 점, 개선할 점

• 조금 더 빠르게 돌아가는 이상하게 생긴 코드가 있는데 어떤 건지는 잘 모르겠지만... 흠 저번에 친구가 알려준 세그먼트 트리의 발전형인 것 같은데... 아무튼 아래에 링크해두었다.

 

<코드>

#include <iostream>
#include <cmath>

using namespace std;
typedef long long ll;

const int MAX_N = 1000001;
const int MAX_Node = 1 << 21;

int N, M;
ll num[MAX_N];
ll tree[MAX_Node], lazy[MAX_Node];

void init(int node, int start, int end) {
    if(start == end)
        tree[node] = num[start];
    else {
        init(node*2, start, (start+end)/2);
        init(node*2+1, (start+end)/2+1, end);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
}

void update_lazy(int node, int start, int end) {
    if(lazy[node]) {
        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 update_range(int node, int start, int end, int left, int right, ll diff) {
    update_lazy(node, start, end);
    if(end < left || right < start)
        return;
    if(left <= start && end <= right) {
        tree[node] += (end-start+1)*diff;
        if(end != start) {
            lazy[node*2] += diff;
            lazy[node*2+1] += diff;
        }
        return;
    }
    update_range(node*2, start, (start+end)/2, left, right, diff);
    update_range(node*2+1, (start+end)/2+1, end, left, right, diff);
    tree[node] = tree[node*2] + tree[node*2+1];
}

ll query(int node, int start, int end, int left, int right) {
    update_lazy(node, start, end);
    if(end < left || right < start)
        return 0;
    if(left <= start && end <= right)
        return tree[node];
    ll lsum = query(node*2, start, (start+end)/2, left, right);
    ll rsum = query(node*2+1, (start+end)/2+1, end, left, right);
    return lsum + rsum;
}

void input() {
    cin >> N;
    
    for(int i=0; i<N; i++)
        cin >> num[i];
    
    cin >> M;
    
    init(1, 0, N-1);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    while(M--) {
        int what;
        cin >> what;
        if(what == 1) {
            int left, right;
            ll diff;
            cin >> left >> right >> diff;
            update_range(1, 0, N-1, left-1, right-1, diff);
        }
        if(what == 2) {
            int left;
            cin >> left;
            cout << query(1, 0, N-1, left-1, left-1) << '\n';
        }
    }
    
    
    return 0;
}

 

 

<참고한 코드(풀어야 볼 수 있습니다.)>

https://www.acmicpc.net/source/30385025

로그인

 

<느리게 갱신되는 세그먼트 트리>

https://book.acmicpc.net/ds/segment-tree-lazy-propagation

느리게 갱신되는 세그먼트 트리

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.