1. 세그먼트 트리 크기 구하기
n = 12일 때, 2^k로 12보다 바로 큰 값을 만들 수 있는 k는 4
2^k를 하면 16이 되고, 16에 *2를 하면, 세그먼트 트리의 크기
만약, 간단하게 하고 싶다면, 그냥 n * 4를하면 된다. (12*4 = 48)
다만, 요렇게 하면 메모리를 조금 낭비하게 된다. (32<48)
int h = (int)ceil(log2(n));
int treeSize = (1 << (h + 1)); // pow(2, h)*2; 보다 직관적인 방법
2. 소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#define _CRT_SECURE_NO_WARNINGS
#define INF 987654321
#include <iostream>
using namespace std;
int arr[10] = { 1, 4, 6, 8, 2, 3, 9, 10, 5, 7 };
const int TREE_NUM = 10;
int tree[4 * TREE_NUM]; // 간단하게 크기를 구하기 위해 배열 원소의 갯수에 4를 곱했다.
int init(int s, int e, int node) {
if (s == e) return tree[node] = arr[s];
int mid = (s + e) / 2;
return tree[node] = init(s, mid, node * 2) + init(mid + 1, e, node * 2 + 1);
}
int sum(int s, int e, int node, int left, int right) {
if (left > e || right < s) return 0;
if (left <= s && right >= e) return tree[node];
int mid = (s + e) / 2;
return sum(s, mid, node * 2, left, right) + sum(mid + 1, e, node * 2 + 1, left, right);
}
void update(int s, int e, int node, int index, int diff) {
if (index<s || index >e) return;
tree[node] += diff;
if (s == e) return;
int mid = (s + e) / 2;
update(s, mid, node * 2, index, diff);
update(mid + 1, e, node * 2 + 1, index, diff);
}
int main() {
init(0, TREE_NUM - 1, 1); // 세그먼트 트리 생성
cout << sum(0, 9, 1, 0, 9) << endl; // 인덱스 0~9 범위 구간 합
cout << sum(0, 9, 1, 3, 5) << endl; // 인덱스 3~5 범위 구간 합
update(0, 9, 1, 4, -1); // 인덱스 4의 원소 -1
cout << sum(0, 9, 1, 3, 5) << endl; // 인덱스 3~5 범위 구간 합
return 0;
}
|
cs |
https://www.acmicpc.net/problem/2042
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
https://www.acmicpc.net/problem/11505
11505번: 구간 곱 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
https://www.acmicpc.net/problem/2357
2357번: 최솟값과 최댓값
N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100
www.acmicpc.net
https://www.acmicpc.net/problem/2268
2268번: 수들의 합
첫째 줄에는 N(1≤N≤1,000,000), M(1≤M≤1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는지를
www.acmicpc.net
https://www.acmicpc.net/problem/3006
3006번: 터보소트
첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이며, 배열의 크기이다. 둘째 줄부터 N개의 줄에는 1보다 크거나 같고, N보다 작거나 같은 수가 중복 없이 주어진다
www.acmicpc.net
https://www.acmicpc.net/problem/1280
1280번: 나무 심기
첫째 줄에 나무의 개수 N (2 ≤ N ≤ 200,000)이 주어진다. 둘째 줄부터 N개의 줄에 1번 나무의 좌표부터 차례대로 주어진다. 각각의 좌표는 200,000보다 작은 자연수 또는 0이다.
www.acmicpc.net
https://www.acmicpc.net/problem/3653
3653번: 영화 수집
각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD
www.acmicpc.net
'자료구조 + 알고리즘' 카테고리의 다른 글
| 비트 마스킹 (0) | 2021.09.13 |
|---|---|
| 인덱스 트리 (0) | 2021.09.13 |
| 슬라이딩 윈도우 (0) | 2021.09.13 |
| 구간합(Prefix sum), 투 포인터 (0) | 2021.09.13 |
| 이분탐색 (Binary Search) (0) | 2021.09.13 |