세그먼트 트리

[Jinsun-Lee]

리드미

• 2042. 구간 합 구하기 (개념)
  1. Sqrt Decomposition
  2. Top-Down Segment Tree
  3. Dynamic Segment Tree
  4. Bottom-Up Segment Tree
  5. Top-Down Segment Tree with Lazy Propagation

[Jinsun-Lee]

추가 풀이한 문제 (리드미에 없음)

• [x]

[Jinsun-Lee]

11659. 구간 합 구하기 4

#include <iostream>
using namespace std;

int psum[100'001];

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int N, M; cin >> N >> M;
    
    for (int i = 1; i <= N; ++i) {
        cin >> psum[i];
        psum[i]+=psum[i-1];
    }

    int a, b;
    while(M--){
        cin >> a >> b;
        cout << psum[b]-psum[a-1] <<"\n";
    }
    return 0;
}

[Jinsun-Lee]

2042. 구간 합 구하기 (코드)

1. Top - Down Segment Tree: 탑다운 / 1기반 / diff 이용, 내려가면서 val만큼 증가
2. Top - Down Segment Tree: 탑다운 / 0기반 / 위와 동일
3. Top - Down Segment Tree: 탑다운 / 0기반 / 새로운값, 먼저 내려간 다음에 값 바꾸고 올라가면서 합 다시 구함
4. Dynamic Segment Tree: 탑다운 / 0기반 / 위와 동일, 다이나믹으로 트리의 크기를 필요한 만큼 잡는 게 달라
5. Dynamic Segment Tree: 탑다운 / 0기반 / 위와 동일, 다이나믹을 포인터 기반의 링크드리스트로 구현함
6. ⭐Bottom-Up Segment Tree: 바텀업 / 0기반 / 위에 것들보다 훨 좋아... 근데 아래 것이 더 좋아
7. ⭐Bottom-Up Segment Tree: 바텀업 / 0기반 / 짱짱
8. Top - Down Segment Tree with Lazy Propagation: 탑다운 / 0기반 / LAZY, 이 문제에서는 핵구려짐

[Jinsun-Lee]

10999. 구간 합 구하기 2 (코드)

1. ⭐⭐Top - Down Segment Tree with Lazy Propagation: 탑다운 / 0기반 / LAZY

[Jinsun-Lee]

Persistent Segment Tree

Egg 문제, 풀이