# lazy propagation

15개의 포스트
post-thumbnail

BOJ 13925 | 수열과 쿼리 13

길이가 N인 수열에서 4가지 쿼리를 적절하게 처리하는 문제입니다. 구간 덧셈, 구간 곱셈, 구간 변경 연산과 구간 합을 출력하는 쿼리가 들어있습니다. 구간 덧셈과 곱셈, 그리고 변경은 전부 update() 연산이고, lazy하게 처리하는 방법이 조금 떠올리기 어렵습니다. 그러나 그건 tree[node] += lazy[node] 같이 단순히 레이지 값을 더하거나 곱하는 방법으로만 세그먼트 트리를 작성해봐서 그렇습니다. lazy 값을 관리하고, 적용하는 다양한 방법을 연습해보고 이 문제에 도전하시는 것을 추천드립니다. > 해결 방법 어떤 노드가 push() 될 때, 그 노드는 레이지 값을 반영합니다. 덧셈 쿼리로 인한 lazy와 곱셈 쿼리로 인한 lazy가 겹쳐서 반영된 상태에서 올바르게 처리하려면 어떻게 l

2023년 5월 29일
·
0개의 댓글
·
post-thumbnail

BOJ 1395 | 스위치

일단 이 문제는 $O(N^2/64)$로 뚫린다고 합니다. Bitset으로 날먹할 수 있습니다. 스위치의 값은 0과 1 중 하나라는 점이 중요 포인트입니다. query() 가 합을 구하도록 되어 있으니 구간 합 세그트리를 구성해야 합니다. lazy는 boolean 값을 담도록 합니다. 0이면 반전시킬 필요가 없고, 1이면 반전시켜야 합니다. update()는 tag_condition일 때 lazy를 반전시키고, push() 합니다. push()는 리프 노드일 때는 tree[node]를 반전시키고, 리프 노드가 아니라면 자식 노드에 먼저 전파한 뒤, 자식 노드의 lazy 값을 반영해서 tree[node] 값을 재구성합니다. tree[node] = tree[node2] + tree[node2+1] 이지

2023년 5월 28일
·
0개의 댓글
·
post-thumbnail

BOJ 12844 | XOR

https://www.acmicpc.net/problem/12844 레이지 프로퍼게이션을 쓰는 연습 문제입니다. XOR 연산은 합 연산과 다르게 구간 [s, e]에 대해 (e-s+1) 이 홀수일 때만 노드에 lazy를 xor해주면 됩니다. 0^a = a a^a = 0 x^a^a = x 인 점을 생각해서 코드를 짜면 됩니다. 원래는 여러 조건도 빠져 있고 데이터도 말썽이 심했다고 들었는데 지금은 일반적인 연습문제가 된 것 같습니다. > 코드

2023년 5월 28일
·
0개의 댓글
·
post-thumbnail

Fenwick Tree(Binary Indexed Tree)

Fenwick Tree (BIT) 2진법 인덱스 구조를 이용해 구간합을 빠르게 구하기 위한 자료구조 0이 아닌 마지막 비트를 구하는 방법 : 특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해선 -K & K 계산 ✅ 해설 index가 1부터 시작한다는 가정 하에 1번 index : fenwick tree[1] = ary[1]이다. 6번 index : fenwick tree[6] = ary[6] + ary[5] 8번 index : fenwick tree[8] = ary[8] + ary[7] + ... + ary[1] > 펜윅 트리에서 사용하는 수식 : LB[i] = i & -i (&는 비트연산, -i = ~i + 1) -> 가장 뒤에 나오는 1이 위치한 구하는 식이다. ![](https://ve

2022년 5월 26일
·
0개의 댓글
·

[알고리즘] Lazy Propagation

📌 선행 개념 해당 알고리즘은 세그먼트 트리에 대한 이해가 필요한 알고리즘입니다. 세그먼트 트리 📌 범위 업데이트에 대한 세그먼트 트리 시간 복잡도 세그먼트 트리의 장점은 부분에 대한 정보를 가지고 있다는 점이고, 특정 index의 원소가 변경되어도 그 index가 포함된 부분의 정보만 수정하면 되기 때문에 간단합니다. 그러나 한 번에 여러 개의 노드의 정보가 변경된다면 시간 복잡도는 크게 증가합니다. 단일 노드에 대한 갱신 시간 복잡도는 O(logN)이었습니다. 이것이 범위로 확장된다면 O(NlogN)이 됩니다. 구간의 크기 만큼 leaf 노드까지 방문해야 하기 때문입니다. 이러한 갱신의 횟수가 증가하면 증가할수록 시간복잡도는 크게 증가

2022년 4월 4일
·
0개의 댓글
·
post-thumbnail

[PS] 백준 10999- 구간 합 구하기 2

📌 알고리즘 분류 해당 문제는 세그먼트 트리 알고리즘에 대한 이해가 필요한 문제입니다. 해당 문제는 Lazy propagation 알고리즘에 대한 이해가 필요한 문제입니다 - 추가예정 세그먼트 트리 📖 문제 백준 10999 💻 코드 ![](https://media.vlpt.us/images/hwan2da/post/13d999ef-27f5-4793-a2c9-0a2635a0b8c5/c

2022년 4월 2일
·
0개의 댓글
·

2820. 자동차 공장

문제 시간 제한: 1초 메모리 제한: 256MB Problem Analysis 많은 부하를 빠르게 갱신해야 하는데, naive 하게 풀면 최대 O(N)이다. lazy propagation을 이용하면 O(logN)으로 줄일 수 있을 것이다. 그런데 문제는, 부하의 범위가 연속적이지 않을 수 있다는 점이다. 부하의 번호만 연속적으로 바꿀 수 있다면, lazy로

2022년 3월 25일
·
0개의 댓글
·

Lazy Propagation

Lazy Propagation In Segment Tree > 일부 updates를 미루면서, 구간 updates를 최적화 시키는 알고리즘 Problem 위의 그림은, 구간의 합을 저장하는 Segment Tree이다. 이를 통해, 하나의 값을 갱신할 때, 구간의 합도 O(logN)이라는 빠른 시간 안에 update 할 수 있다. 그러나, 값 하나를 update 하는 게 아니라, 특정 range의 모든 값들을 update해야 한다면 어떨까? range가 M이라고 할 때 O(MlogN)이 걸린다. 물론, 기본 Segment Tree도 빠르지만, 이런 상황이 계속 주어지면 많은 시간을 요구하게 된다. Soluti

2022년 3월 13일
·
0개의 댓글
·
post-thumbnail

백준 24527번: 이상한 나라의 갈톤보드

이상한 나라의 갈톤보드 백준 24527번: 이상한 나라의 갈톤보드 아이디어 맨 처음 생각한 아이디어는 그냥 레이지 세그로 푸는거였다. 구간 업데이트와 쿼리를 로그 시간에 처리할 수 있기 때문에 무난하게 통과할 수 있다. 누적합 응용으로 imos법이라는게 있다. a부터 b까지 3을 더한다 하면, diff[a] += 3, diff[b+1] -= 3을 한다. 즉, 차이를 기록한다. 이를 통해 아무리 긴 구간에 더해지는 연산도 상수 시간에 처리할 수 있고, 이를 앞에서부터 더하면서 누적합으로 복원하면 된다. 시작지점 번호가 주어지면, 전체 삼각형에서 맨 오른쪽 값을 미리 저장해둔 벡터에서 이분탐색을 하여 몇층인지 구할 수

2022년 3월 1일
·
4개의 댓글
·

알고리즘 스터디 - 3주차

'22. 2. 11. 알고리즘 스터디 내용 및 회고 > #### 주제 > 1. Segment Tree(lazy propagation) > 2. 백준 10999번(lazy propagation을 이용한 문제) Segment Tree(lazy propagation) > Segment Tree에서 구간 업데이트를 빠르게 하기 위해 적용한 lazy propagation에 대해 공부하였음. 컴퓨터구조에서 배운 캐시의 개념과 비슷하게 생각하였음. > 참고 : https://bowbowbow.tistory.com/4 1. 문제점 구간에 대해 업데이트를 한꺼번에 실행할 때, 기존 segment tree를 이용할 경우 모든 node를 거쳐가며 업데이트를 해줘야한다. 이때 한 개의 업데이트는 ($log2(n)$)이 걸리는데, 여기서 m의 길이의 구간을 업데이트 한다고 할 때 ($m * log2(n)$)가 된다

2022년 2월 17일
·
0개의 댓글
·
post-thumbnail

백준 13925번: 수열과 쿼리 13

수열과 쿼리 13 백준 13925번: 수열과 쿼리 아이디어 구간에 더하기, 곱하기 교체 세가지 쿼리를 모두 수행해야 한다. ax + b꼴로 lazy를 만들고, 곱셈 쿼리가 들어오면 a\=v, b\=v, 덧셈 쿼리가 들어오면 b+=v, 교체 쿼리가 들어오면 a\=0, b\=,0, b+=v 를 해주면 된다! 코드 여담 > 모듈로 연산을 잘 해야한다. propagate 짤 때 자꾸 생각없이 짜서 그냥 아래로 전파해버리는데 조심해야겠다. 다이아몬드 문제를 풀다니.. 감격..

2021년 12월 11일
·
0개의 댓글
·

백준 1395번: 스위치

스위치 백준 1395번: 스위치 아이디어 tree에는 켜져있는 스위치의 개수를 기록한다. lazy에는 반전을 몇번이나 해야 하는지 기록해둔다. 두 번 반전하면 똑같아지므로 lazy[node]가 홀수인 경우만 반전을 해주면 된다. 반전이 일어나는 경우 현재 구간 사이즈를 재서 몇개를 켜진 상태로 만들어야 하는지 알아낼 수 있다. 코드 여담 > 1트에 풀어버림 ㄷㄷ 풀면서 느낀건데 update는 void로 짜는게 왠지모르게 더 편하다.

2021년 12월 8일
·
2개의 댓글
·

백준 12844번: XOR

XOR 백준 12844번: XOR 아이디어 XOR 연산은 결합법칙과 교환법칙이 성립한다. 따라서 구간합 세그먼트 트리처럼 구성할 수 있다. 코드 여담 > lazy[node*2] ^= lazy[node] 해야하는데 +=을 써버렸다. 상위 노드만 연속으로 방문해서 자식 노드에 업데이트 해야하는 내용이 쌓일 수 있기 때문에 항상 0이라는 보장을 할 수 없다. 주의하도록 하자..!

2021년 12월 7일
·
0개의 댓글
·

백준 10999번: 구간 합 구하기 2

구간 합 구하기 2 백준 10999번: 구간 합 구하기 2 아이디어 구간의 길이가 최대 N이므로 구간에 존재하는 모든 노드를 바꾸려면 NlogN이 걸린다. 해당 구간에 존재하는 모든 노드를 업데이트하지 말고, 이 노드는 업데이트가 필요합니다! 라고 표시만 해놓고 나중에 방문할 때 업데이트를 해주면 어떨까? 딱 맞는 구간까지만 업데이트하고, 그 구간을 표시하는 노드의 left, right child에 표시를 해둔다. 나중에 그 child를 방문했을 때, 값을 업데이트하고, 다시 left, right child에 표시를(리프 노드라면 못하겠죠?) 해 둔다. 이렇게 하면 업데이트를 로그 시간에 진행할 수 있다!! 백준 선생님이 아주 야무지게 설명해주시는 세그먼트 트리 나중에 업데이트 해야지!를 읽어보자. propaga

2021년 12월 7일
·
0개의 댓글
·
post-thumbnail

[알고리즘] 백준 10999

문제 숫자 배열이 주어지고 구간의 합을 구하는 문제다. 단순히보면 이전의 구간합과 비슷한데 문제는 구간을 통채로 더하는 연산이 존재한다. n이 10^6이고 구간변경이 10^4이기에 1초(약10^8)는 그냥 넘어간다. (먼저 그렇게 제출해서 시간초과가 나왔다.) lazy propagation 나는 세그먼트 트리 문제를 구현이 간단한 인덱스 트리로 계산한다. 세그먼트 트리는 루트 노드부터 내려오고 인덱스 트리는 리프 노드부터 올라가는 성질이 있다. 이게 왜 중요하냐면 lazy propagation 자체 개념이 구간의

2021년 7월 28일
·
0개의 댓글
·