segment tree2 [백준 C++] 2042번: 구간 합 구하기 1. 문제https://www.acmicpc.net/problem/2042 2. 알고리즘 분류자료 구조세그먼트 트리 3. 소스 코드#include #define MAX_N 1000006using namespace std;typedef long long ll;int N, M, K;ll arr[MAX_N];ll tree[4 * MAX_N];// Segment Tree 생성 함수ll init(int node, int start, int end) { // leaf node인 경우, if (start == end) return tree[node] = arr[start]; int mid = (start + end) / 2; int child_node1 = 2 * node; int child_node2 = 2 * n.. 2024. 9. 13. [자료구조] Segment Tree(세그먼트 트리) 1. Segment Tree(세그먼트 트리) Segment Tree(세그먼트 트리)는 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조입니다. Segment Tree를 도식화하면, 아래와 같습니다. Segment Tree는 다양한 활용법이 있겠지만, 특히 특정 데이터 배열의 구간 합을 계산할 때 유용합니다. 아래 예시를 통해, 단순 배열 방법과 Segment Tree 활용법을 비교해보겠습니다. 예시 1) 단순 배열 방법 array = {1, 2, 3, ..., N} 배열에서 특정 범위의 구간 합과 특정 인덱스의 값 변경을 M번 수행 (1) array 배열에서 1번째 ~ N번째까지 구간 합 연산S = array[0] + array[1] + array[2] + ... + array[N - 1]시간 복.. 2024. 9. 12. 이전 1 다음
