segment tree5 백준 11505 : 구간 곱 구하기 (C++) [Segment tree] Segment tree에서 최소값, 최대값 구하는 것보다 조금은 더 생각해야 하는 것 같다. **문제풀이 방법 - Tree 생성, 업데이트, query 연산(곱하기) 함수 작성 ***코드 #include #include #include #define denum 1000000007 #define MAX_N 1000001 typedef long long int ll; using namespace std; // start, end : node가 담당하고 있는 구간 // left, right : 계산을 하려는 구간 int N, M, K; vectorarr; vectorsegment_tree; // Segment tree 초기화 ll build_segment_tree(int node, int start, int .. 2022. 4. 2. 백준 2357 : 최솟값과 최댓값 (C++) [Segment tree] 최솟값만 구하던 문제와 같은 방식으로 풀면 된다. 다만 두 개의 값을 반환하기 위해 segment tree를 각각 만들어서 진행한다. **문제풀이 방법 - 최솟값을 구하기 위한 segment tree와 최댓값을 구하기 위한 segment tree를 각각 만들고, 연산하는 것도 각각 연산 ***코드 #include #include #include #include #define INF 2e9 #define MAX_N 100001 using namespace std; int N, M; int min_value, max_value; vectorarr; vectorsegment_tree_min; vectorsegment_tree_max; int build_segment_tree_min(int node, int s.. 2022. 4. 1. 백준 10868 : 최솟값 (C++) [Segment tree] 세그먼트 트리를 연습할 수 있는 좋은 기본 예제이다. **문제풀이 방법 - 새로운 값이 들어와서 트리가 바뀌는 업데이트가 없으므로, 트리 생성과 최소값을 구하는 함수만 작성 ***코드 #include #include #include #include #define INF 2e9 #define MAX_N 100001 using namespace std; int N, M; vector arr; vector segment_tree; int min_value; int build_segment_tree(int node, int start, int end) { if (start == end) { segment_tree[node] = arr[start]; return segment_tree[node]; } int le.. 2022. 4. 1. 백준 2042 : 구간 합 구하기 (C++) [Segment tree] 기본적인 segment tree를 연습해 볼 수 있는 문제이다. **문제풀이 방법 - Segment tree 생성, 새 값이 들어왔을 때 update 함수, 합을 구하는 함수 작성 ***코드 #include #include #include typedef long long int ll; using namespace std; // start, end : node가 담당하고 있는 구간 // left, right : 합을 구하려는 구간 // Segment tree 초기화 ll init(vector& arr, vector& tree, int node, int start, int end) { if (start == end) { return tree[node] = arr[start]; } else { int mid .. 2022. 4. 1. 이전 1 2 다음