[C++] 10999번 구간 합 구하기 2 - 자료 구조, 세그먼트 트리, 느리게 갱신되는 세그먼트 트리

거의 똑같은 문제인 16975번 수열과 트리 21과 함께 풀이됩니다.

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>
#include <vector>

using namespace std;
typedef long long ll;

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

//수의 개수 N, 수의 변경이 일어나는 횟수 M, 구간의 합을 구하는 횟수 K
int N, M, K;
//수열
ll num[MAX_N];
//세그먼트 트리와 세그먼트 트리용 lazy
ll tree[MAX_Node], lazy[MAX_Node];

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

//세그먼트 트리 생성
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];
    }
}

//lazy값 더해주기
void update_lazy(int node, int start, int end) {
    if(lazy[node]) {
        //구성 원소 개수 만큼 lazy[node] 더해주기
        tree[node] += (end-start+1)*lazy[node];
        //아래 구성 원소에 lazy 추가하기
        if(start != end) {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0;
    }
}

//end~left 값에 diff 더해주기
void update_range(int node, int start, int end, int left, int right, ll diff) {
    //lazy가 있으면 더해주기
    update_lazy(node, start, end);
    if(left > end || right < start)
        return;
    //범위에 있으면 더해주기
    if(left <= start && end <= right) {
        tree[node] += (end-start+1)*diff;
        if(start != end) {
            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) {
    //lazy가 있으면 더해주기
    update_lazy(node, start, end);
    if(left > end || right < start)
        return 0;
    //범위에 있으면 바로 return
    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;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    //세그먼트 트리 생성
    init(1, 0, N-1);
    
    while(M--) {
        int a;
        cin >> a;
        
        if(a == 1) {
            int b, c;
            ll d;
            cin >> b >> c >> d;
            //b~c에 d 더해주기
            update_range(1, 0, N-1, b-1, c-1, d);
        }
        if(a == 2) {
            int b, c;
            cin >> b >> c;
            //b~c의 구간합 출력하기
            cout << query(1, 0, N-1, b-1, c-1) << '\n';
        }
    }
    
    return 0;
}

 

 

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

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

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

 

<ceil() 함수>

https://blockdmask.tistory.com/112

[C언어/C++] 올림, 내림, 반올림 (floor, ceil) 함수

 

 

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