# lazy propagation

12개의 포스트
post-thumbnail

Fenwick Tree(Binary Indexed Tree)

Fenwick Tree (BIT)2진법 인덱스 구조를 이용해 구간합을 빠르게 구하기 위한 자료구조0이 아닌 마지막 비트를 구하는 방법: 특정한 숫자 K의 0이 아닌 마지막 비트를 찾기 위해선 -K & K 계산index가 1부터 시작한다는 가정 하에1번 index : f

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

[알고리즘] Lazy Propagation

[알고리즘] Lazy Propagation

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

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

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

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

2820. 자동차 공장

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

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

Lazy Propagation

updates를 미루면서, 구간 updates를 최적화 시키는 알고리즘위의 그림은, 구간의 합을 저장하는 Segment Tree이다. 이를 통해서, 하나의 값뿐만 아니라, 동시에 구간의 합도 O(logN)이라는 빠른 시간 안에 update 할 수 있다.그러나, 값 하나

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

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

백준 24527번: 이상한 나라의 갈톤보드맨 처음 생각한 아이디어는 그냥 레이지 세그로 푸는거였다. 구간 업데이트를 로그 시간에 처리하고, 쿼리에 대답할 때는 누적합으로 상수 시간에 대답했다. 누적합 응용으로 imos법이라는게 있다. a부터 b까지 3을 더한다 하면,

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

알고리즘 스터디 - 3주차

Segment Tree(lazy propagation)백준 10999번(lazy propagation을 이용한 문제)Segment Tree에서 구간 업데이트를 빠르게 하기 위해 적용한 lazy propagation에 대해 공부하였음.컴퓨터구조에서 배운 캐시의 개념과 비

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

백준 13925번: 수열과 쿼리 13

백준 13925번: 수열과 쿼리구간에 더하기, 곱하기 교체 세가지 쿼리를 모두 수행해야 한다. ax + b꼴로 lazy를 만들고, 곱셈 쿼리가 들어오면 a*=v, b*=v, 덧셈 쿼리가 들어오면 b+=v, 교체 쿼리가 들어오면 a*=0, b*=,0, b+=v 를 해주면

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

백준 1395번: 스위치

스위치 백준 1395번: 스위치 아이디어 tree에는 켜져있는 스위치의 개수를 기록한다. lazy에는 반전을 몇번이나 해야 하는지 기록해둔다. 두 번 반전하면 똑같아지므로 lazy[node]가 홀수인 경우만 반전을 해주면 된다. 반전이 일어나는 경우 현재 구간 사이

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

백준 12844번: XOR

백준 12844번: XORXOR 연산은 결합법칙과 교환법칙이 성립한다. 따라서 구간합 세그먼트 트리처럼 구성할 수 있다. lazynode\*2 ^= lazynode 해야하는데 +=을 써버렸다. 상위 노드만 연속으로 방문해서 자식 노드에 업데이트 해야하는 내용이 쌓일 수

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

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

백준 10999번: 구간 합 구하기 2구간의 길이가 최대 N이므로 구간에 존재하는 모든 노드를 바꾸려면 NlogN이 걸린다. 해당 구간에 존재하는 모든 노드를 업데이트하지 말고, 이 노드는 업데이트가 필요합니다! 라고 표시만 해놓고 나중에 방문할 때 업데이트를 해주면

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

[알고리즘] 백준 10999

세그먼트 트리와 lazy propagation

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