펜윅트리로 '세그먼트 트리 느리게 업데이트 하기(Lazy Propagation)' 구현하기(2934 LRH식물 펜윅트리)

https://www.acmicpc.net/blog/view/88

펜윅 트리 200% 활용하기

https://blog.naver.com/jh05013/221475142152

BOJ 16975부터 16979까지

 

이 두 개를 보고도 이해가 안 됐는데 드디어 이해해서 정리 글을 씁니다

 

아래서부터 펜윅트리 200% 활용하기를 1번글 boj 16975글을 2번글이라고 함

 

솔직히 처음에는 1번글에서 나온 일반식이 2번글 풀이와 뭐가 같은 건지 잘 모르겠었음

근데 같은 사람이 적은 글이긴 한데 1번글 아래 실제 구현할 때 쓰는 식과 다르다고 적혀있으니까

1번은 그런 방법도 있구나 하고 이해하고 넘어가면 될 것 같음

 

 

1번은 설명이 잘 되어있으니까 2번만 다뤄보겠읍니다

2번이 말하는 방법은 쿼리를 두 번 보내는 것

 

[a,b]에 x를 더하는 쿼리를 2개의 쿼리로 나눔

즉 update를 하는데 a에 x를 더하는 쿼리/b+1에 -x를 더하는 쿼리 두 번 해준다

 

이게 무슨 말이냐 쉽게 설명하면

[a,b]구간에 1을 더한다고 칠 때

update(tree, a, 1)을 하면 a부터 끝까지 1이 더하지는데

update(tree, b+1, -1)을 하면 b+1부터 끝까지 -1이 더해짐

그러면 결과적으로 a~b까지 1을 더한 거랑 마찬가지가 된다

 

이 방법이 a~b에다가 for문으로 update를 하는 것보다 훨씬 빠름 update를 딱 두 번만 하니까

 

내 머릿속에는 인덱스 트리가 점령하고 있어가지고 1<<n부터 0으로 거꾸로 오면서 업데이트 해야 되는데 어떻게 저렇게 되지? 그러면서 이해가 안 됐는데

펜윅트리는 앞에서부터 뒤로 가면서 업데이트 한다는 사실을 헷갈려서 그랬음 바보

 

펜윅트리를 이렇게 쓰는 방법은 솔직히 수열과 쿼리 21보다 LRH식물이 더 이해가 잘 됨

https://www.acmicpc.net/problem/2934

2934번: LRH 식물

이 문제는 사각형 반짜리가 서로 겹치는 부분의 수를 구하는 문제

이 글이랑 같이 읽으면 도움이 될 듯(https://toujours.tistory.com/entry/2934LRH-%EC%8B%9D%EB%AC%BC)

다만 저 글에서 처음에 배열이 변화하는 과정을 설명해주는데 인덱스가 약간 틀렸음 그것만 주의해서 보면 됨

 

 

저 글에서 설명 잘 했지만 좀 더 풀어서 설명하자면 수평선을 놓는다고 생각하면 됨

양 끝값을 제외한 유효한 곳에 수평선을 놓고(수평선을 놓는다는 의미: 그 길이 부분은 1씩 더해진다)

a,b입력 받아서 해당 위치의 값을 출력하고 0으로 바꿈

왜 a, b부분만 하냐면 그 전 수평선과 겹쳐질 수 있는 부분은 a, b의 아래로 향하는 직선 뿐이기 때문(직접 그래프 그려보면 바로 이해 됨)

a, b부분을 0으로 하는 이유는 꽃을 이미 셌기 때문이다 중복ㄴㄴ해

 

그래서 세그트리의 역할은 수평선이 존재하는 위치를 알려주는 트리가 된다

코드 참고: https://github.com/proqk/Algorithm/blob/master/Segment%20Tree/2934%20LRH%20%EC%8B%9D%EB%AC%BC(%ED%8E%9C%EC%9C%85%20%ED%8A%B8%EB%A6%AC).cpp

proqk/Algorithm

다만 이런 방식은 구간에 v를 더하고 한 점의 값을 받아오는 쿼리일 때만 가능한 

이런 방법 자체가 '구간에 v를 더하고 한 점의 값을 받아오는 쿼리' 를 '한 점에 v를 더하고 구간의 합을 받아오는 쿼리'로 바꾸는 거라서

구간에 v를 더하고 구간의 값을 받아오는 쿼리로도 사용할 수 있나.. 그건 좀 더 공부해서 알아봐야 되겠다->

(수정)구간에 v를 더하고 구간의 값을 받아오는 쿼리로도 사용할 수 있다(펜윅 트리 200% 활용하기글 참고)

 

참고) 구간에 v를 더하고 구간의 값을 받아오는 쿼리 문제: https://www.acmicpc.net/problem/10999