티스토리

하루 코딩

검색하기

블로그 홈

하루 코딩

onedaycoding.tistory.com/m

jhg0406 님의 블로그입니다.

구독자: 0

방명록 방문하기

주요 글 목록

Segment with Lazy Propagation Lazy Propagation 세그먼트 트리에서 구간을 업데이트 할때, 해당하는 모든 노드를 업데이트 해주는것은 최대 O(nlgn) 만큼 시간이 걸리는데 Lazy Propagation을 사용하면 O(lgn) 시간안에 업데이트를 할수 있습니다. 이를 위해 lazy라는 배열이 필요하고, lazy에는 해당 idx에 해당하는 트리의 노드에 업데이트 되어야 할 값이 들어가게 됩니다. https://www.acmicpc.net/problem/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터.. 공감수 0 댓글수 0 2020. 4. 6.
Segment Tree 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 63 64 65 66 67 68 69 70 //segment tree //배열의 구간 최소 쿼리를 해결하기 위한 구간 트리의 구현 struct RMQ { //배열의 길이 int n; //각 구간의 최소치 vector rangeMin; RMQ(const vector& arr) { n = arr.size(); rangeMin.resize(n*4); init(arr, 0, n-1, 1); } //n.. 공감수 0 댓글수 0 2020. 3. 13.
펜윅트리 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 //펜윅 트리의 완전한 구현 //펜윅 트리의 구현, 가상의 배열 A[]의 부분 합을 //빠르게 구현할 수 있도록 한다. 초기화시에는 A[]의 //원소가 전부 0이라고 생각한다 struct FenwickTree { vector tree; FenwickTree(int n) : tree(n+1) {} //A[0...pos]의 부분 합을 구한다. int sum(int pos) { //인덱스가 1부터 시작한다고 생각하자. ++pos; int ret = 0; while(pos > 0) { ret += tree[pos]; //다음 구간을 찾기.. 공감수 0 댓글수 0 2020. 3. 5.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.