surkim 님의 블로그

구간에서 특정 값보다 큰 값의 개수 구하기구간에서 특정 값보다 작은 값의 개수 구하기구간에서 특정 값의 개수 구하기구간에서 특정 범위에 속하는 값들의 개수 구하기구간에서 k번째 큰,작은 값 구하기구간 내 중복된 값 찾기구간에서 특정 값의 등장 여부 확인 #include #include #include using namespace std;class MergeSortTree {public: MergeSortTree(const vector& arr) { n = arr.size(); tree.resize(4 * n); build(arr, 1, 0, n - 1); } int query(int left, int right, int k) { retur..

세그먼트에서 구간을 빠르게 변경하고 싶을 때class SegmentTree {public: SegmentTree(int size): n(size) { tree.assign(4 * n, 0); lazy.assign(4 * n, 0); } SegmentTree(const vector& arr): n(arr.size()) { tree.assign(4 * n, 0); lazy.assign(4 * n, 0); build(arr, 1, 0, n - 1); } void range_update(int left, int right, long long value) { update_util(1, 0, n - 1, left,..

구간 합구간 곱구간 최솟값구간 최댓값구간 XOR인덱스가 값이 되는 경우, 값이 인덱스가 되는 경우구간 최대, 최소 인덱스 #include using namespace std;// node index 왼쪽 node * 2, 오른쪽 node * 2 + 1// node index는 1부터 시작, vector index는 0부터 시작class SegmentTree {public: SegmentTree(int size): n(size) { tree.assign(4 * n, 0); } SegmentTree(const vector& arr): n(arr.size()) { tree.assign(4 * n, 0); build(arr, 1, 0, n - 1); }..

PS 문제 풀 때 도움될만한 Template을 미리 작성해서 필요할 때마다 가져다 써야겠다. SegmentTree (구간 합)SegmentTree (Lazy propagation)MergeSortTree 백준 옛날에 열심히 했었는데 한동안 손놓고 있었다.이제 가끔씩 심심할 때 풀어야겠다.https://solved.ac/profile/ksro0128 solved.ac알고리즘 문제해결 학습의 이정표 🚩 Baekjoon Online Judge 문제들의 난이도 및 티어 정보를 제공하는 사이트입니다.solved.ac