수열과 쿼리 25 풀이+시간복잡도 증명

수열과 쿼리 25.

 

크기 n의 배열이 존재하고, 쿼리는 3개가 존재한다.

 

1. l r x가 주어지면 구간 (l,r)에 x를 and 연산한다.

 

2. l r x가 주어지면 구간 (l,r)에 x를 or 연산한다.

 

3. l r x가 주어지면 구간 (l,r)에 있는 원소들의 최댓값을 출력한다.

 

1<=N<=200000, 1<=l<=r<=N, 0<=x<2^20이다.

 

SegmentTree Beats 문제로 잘 알려져있다. 하지만 풀이와, 특히 시간복잡도 증명은 잘 알려져있지 않아서 써보려고 한다.

 

SegmentTree Beats의 개념은 원래의 세그먼트 트리로 수행하기 힘든 것을 lazy를 새기는 조건을 약화시키고, 대신 함수를 리턴하는 조건을 강화시켜 시간복잡도를 보장하면서 할 수 있게 만드는 것이다.

 

설명은 귀찮으니 https://justicehui.github.io/hard-algorithm/2019/10/10/segment-tree-beats/로 대체한다.

 

세그먼트 트리 비츠가 뭔지 알아듣기에 좋다. 또 용어도 저기에서 소개된 용어로 다 대체할 거다.

 

그러면 이 문제를 풀기 위해서 우리는 각 노드마다 mx,orv,andv를 저장한다. 각각 노드가 담당하는 구간의 최댓값,그 구간의 수들을 모두 or한 값,그 구간의 수들을 모두 and한 값이다.

 

그리고 이제 업데이트 함수에 대해 다뤄볼 건데, 그 전에 쿼리에 대해 분석해보자. OR쿼리는 x의 비트 중에서 0인 비트는 수에 영향을 끼치지 않는다. 1인 비트는 구간에 대해 그 비트의 숫자를 모두 1로 만든다. AND 쿼리는 반대로 1인 비트는 영향을 끼치지 않고 0인 비트는 구간에 대해 그 비트의 숫자를 모두 0으로 만든다.

 

그럼 먼저 OR쿼리의 업데이트함수를 짜보자. 이걸 짜보고 나면, AND 쿼리의 업데이트함수는 바로 떠오를 것이다.

 

일단 break_condition을 강화시키자. x의 1인 비트에 대해 그 구간의 모든 수의 그 비트가 이미 1이라면, 쿼리는 구간에 전혀 영향을 미치지 못할 것이다. return해주자.

 

그리고 tag_condition을 강화시키자. x의 1인 비트에 대해 그 비트의 숫자가 모두 같을 때에만 tag를 한다. 아니면 그냥 재귀적으로 자식들로 들어간다.

x의 비트는 1이고 구간에서는 그 비트의 모든 숫자가 0으로 같을 경우 그 비트가 모두 1이 되면서 모든 숫자에 대해 k번째 비트일 경우 1<<k가 더해질 것이다. x의 비트가 1이고 구간에서도 그 비트의 모든 숫자가 1로 같으면 아무 일도 없을 것이다.

결국 이 경우 구간의 모든 원소에 대해서 같은 값이 더해짐을 알 수 있다. 그러므로 레이지로 대충 내려주면 우리는 그 레이지값을 토대로 변하게 되는 mx 값을 O(1)에 찾을 수 있다. 새로운 andv와 orv를 찾는 것은 더더욱 쉽다.

 

잘 이해했다면 AND쿼리의 업데이트함수는 이미 깨달았을 것이다. 그러므로 생략한다.

 

또 이때 max값을 구하는 쿼리는 세그먼트 트리의 기초만 알더라도 다 알 거기 때문에 생략한다.

 

코드 또한 생략한다. 설명 듣고 구현해보는 것도 실력에 도움이 꽤 된다.

 

그럼 이제 시간복잡도 증명을 해보겠다.

 

시간복잡도 증명

 

 

원소들의 비트는 각각 20개가 있다. 그 비트에 대해 각각 개별적으로 생각해보자.

우리는 변수 C를 잡는다.

C를 계산하는 방법은 다음과 같다.

모든 20개의 비트들에 대해, 모든 세그먼트 트리에 노드들에 대해 다음의 연산을 수행한다. 그 노드가 담당하는 구간에 해당하는 구간에 대해서 그 비트의 숫자가 모두 같다면 C에 1을, 아니면 C에 2를 더한다.

그러면 C의 값은 언제나 O(20N)을 초과할 수 없음을 쉽게 알 수 있다.

그리고 각각의 쿼리를 생각해보자.

원래도 방문했을 노드들은 무시하고, 원래는 방문하지 않았을 extra node들에 대해 생각한다. ㅣ<=nodel&&noder<=r이라 원래 tag_condition에 걸렸어야 했는데 tag_condition에 걸리지 않은 노드들이다. 그 노드들의 특징은 20개의 비트들 중에서, 구간의 모든 원소에 대해 값이 같지 않은 비트가 하나라도 있다는 것이다. 그러지 않았으면 tag_condition에 걸렸을 것이므로 자명하다. 그리고 update 연산이 완료되었을 때, 적어도 하나의 비트에 대해서 값이 통일되지 않았던 비트가 값이 통일되게 된다. OR쿼리에 예시를 들자면, x가 1인 비트에 대해서 모든 구간의 값이 같지 않은 비트가 하나라도 존재했기에 tag_condition에 걸리지 않은 것이고, update가 완료되면 그 비트는 모든 구간에 대해서 1로 통일된다는 것이다. 그러면 C 값이 최소 1 감소하게 된다.

하지만 C 값이 증가하게 되는 경우도 존재한다. 그렇지만 그 경우는 구간에 걸쳐있는 노드에 대해서인데, 구간에 걸쳐있는 노드는 많아봤자 O(logN)개이다. 세그먼트 트리의 각 높이에 대해서 구간에 딱 걸칠 수 있는 노드는 최대 2개이고, 세그먼트 트리의 높이는 O(logN)임을 생각하자.

그러면 아무리 C 값을 변화시켜봤자 쿼리 한 번에 logN개의 노드의 20개의 비트에 대해 O(20logN) 정도밖에 증가시킬 수 없다.

그럼 C 값은 O(20NlogN)밖에 증가할 수 없고, extra node를 한 번 방문할 때마다 C 값이 최소 1 감소하며, 당연히 C 값은 음수가 될 수 없으니 우리는 extra node를 O(20NlogN)번 이상 방문할 수 없음을 알 수 있다.

 

그러므로 시간복잡도는 O(20NlogN)=O(log(maxai)NlogN)이다.

 

이 증명은 이 댓글의 증명을 많이 참고하여 수열과 쿼리 25에 맞게 수정한 것입니다.

 

일단 푼 다음에 각 잡고 증명한 것이 아니라, 풀기 위해서 실전형으로 증명을 한 것이기 때문에 곳곳에 오류가 있을 수 있습니다. 제보해주시면 감사하겠습니다.