하루 코딩 하루 코딩

Algorithm/세그먼트, 펜윅트리

• Segment with Lazy Propagation

  Algorithm/세그먼트, 펜윅트리 2020. 4. 6. 12:01

  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는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터..

  Read More

• Segment Tree

  Algorithm/세그먼트, 펜윅트리 2020. 3. 13. 18:00

  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..

  Read More

• 펜윅트리

  Algorithm/세그먼트, 펜윅트리 2020. 3. 5. 01:56

  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]; //다음 구간을 찾기..

  Read More