구간 쿼리

• 어떤 1차원 배열 l이 있을 때, a번째부터 b번째까지의 원소들의 대표값, f(l[i:i+n]) 을 효율적으로 계산하는 방법에 대한 내용.
• 기본적인 요령은, 대표적인 몇몇 구간에 대해서 미리 값을 구해 놓은 뒤, 인풋으로 들어온 구간에 대한 처리는 미리 계산된 구간들의 값을 조합해서 계산하는 것이다.
  • 미리 g(l[x_1:y_1]), g(l[x_2:y_2]), …, g(l[x_k:y_k]) 등과 같은 k개의 구간에 대한 g값을 미리 구해서 갖고 있는다. 그리고 f(l[i:i+n])를 h(g(l[x_a1:y_a1]), g(l[x_a2:y_a2]), …, g(l[x_am:y_am])) 으로 계산할 수 있다면, n개의 값 대신 m개의 값만 갖고서 계산이 가능하다는 것이 기본 원리이다.
    • 그냥 아무 처리 없이 배열 그대로 갖고 있는 것은, 길이가 1인 n개의 구간에 대해서만 값을 갖고 있는 것으로 이해할수 있다.
    • 길이가 sqrt(n)인, sqrt(n)개의 구간에 대해서 미리 값을 구해놓은 뒤에, 이것을 이용해서 처리하는 것이 sqrt decomposition 이 다.
    • 길이가 1,2,4,…n 인 2*n 개의 구간에 대해서 미리 값을 구해놓은 뒤에, 이것을 이용해서 처리하는 것이 세그먼트 트리이다.
    • 길이가 1,2,4,…n 인 n개의 구간에 대해서 미리 값을 구해놓은 뒤에, 이것을 이용해서 처리하는 것이 펜윅 트리이다.
    • 길이가 1,2,4,…n 인 nlogn개의 구간에 대해서 미리 값을 구해놓은 뒤에, 이것을 이용해서 처리하는 것이 스파스 테이블이다.
• 구간 쿼리를 처리하는 코드를 작성할 때에는 0-based 배열을 기준으로 하고, 구간은 항상 [beg, end)형태로 표현하는 것으로 통일하겠다.
  • Teferi library도 모두 이것을 기본으로 만든다. FenwickTree, SegmentTree, 등등에 모두 해당한다.
  • 이렇게 되면, 실제로 많은 문제들의 인풋은 1-based array에서 [l, r] 형태로 주어진다. 번거로울수 있지만, 0-based로 바꿔 저장하고, 구간도 [beg, end)로 변환해서 호출하도록 코드를 짜자. beg = l-1, end = r 이 되므로, 코드에서는 보통, query(l-1, r) 형태로 쓰게 된다.

• 트리가 주어지고, 서브트리 안에 포함된 노드들에 대한 쿼리가 주어질때, 이것을 구간 쿼리로 변환해서 처리하기 위해 사용하는 방법이다.
• 이 방법은 트리 노드들을 1차원 배열에 저장하면서 서브트리가 연속된 구간에 배치되도록 한다. 구체적으로는 트리를 루트에서부터 DFS 방식으로 순회하면서 방문하는 노드 순서대로 배열에 추가하면, 서브트리에 해당하는 노드들이 연속된 구간에 배치된다. 또다른 특징은 어떤 서브트리에 해당하는 연속된 구간에서, 그 서브트리의 루트 노드는 구간의 가장 첫번째에 배치된다는 것이다. DFS로 특정 노드를 처음 방문해서 그 노드를 배열에 추가할때의 인덱스와, 그 노드를 떠날때의 배열에 저장된 마지막 값의 인덱스가, 그 노드를 루트로 하는 서브트리에 해당하는 구간의 시작 인덱스와 끝 인덱스가 된다
• 코드는 이런 식이다

  • def euler_tour_technique(tree, root, values):
        values_in_dfs_order = []
        subtree_ranges = [[None, None] for _ in tree]
        for node in tgraph.dfs(tree, root, yields_on_leave=True):        
            if subtree_ranges[node][0] is None:
                subtree_ranges[node][0] = len(values_in_dfs_order)
                values_in_dfs_order.append(values[node])
            else:
                subtree_ranges[node][1] = len(values_in_dfs_order)
        return values_in_dfs_order, subtree_ranges

  • 경우에 따라서 node를 재배열하는 것이 필요 없을 때도 있다 (초기의 node값이 모두 0이라든가 하는 경우). 그러면 nodes_in_dfs_order 대신 그냥 현재 order를 저장할 변수만 있으면 된다.

    • def euler_tour_technique(tree, root):
          subtree_ranges = [[None, None] for _ in tree]
          order = 0
          for node in tgraph.dfs(tree, root, yields_on_leave=True):
              if subtree_ranges[node][0] is None:
                  subtree_ranges[node][0] = order
                  order += 1
              else:
                  subtree_ranges[node][1] = order
          return subtree_ranges

    • 이 뒤에 노드를 재배치해야 한다면 subtree_ranges에 저장된 값으로 복원하는 것도 가능하다

    • values_in_dfs_order = [None] * N
      for node_index, (dfs_order, _) in enumerate(subtree_ranges):
          values_in_dfs_order[dfs_order] = values[node_index]

  • 관련 문제
    • 회사 문화 3 - 오일러 경로 테크닉 + 포인트 업데이트/구간합 쿼리
    • 회사 문화 2 - 오일러 경로 테크닉 + 구간합 업데이트/포인트 쿼리
    • 트리와 색깔 - 오일러 경로 테크닉 + 구간 rank 쿼리
    • Calculate! 2 - 오일러 경로 테크닉 + 구간 XOR 업데이트/XOR 쿼리

• Prefix sum: 전처리 O(N), 쿼리당 O(1)
• 관련 문제
  • 구간 합 구하기 4 (N≤100,000, Q≤100,000)

• Sqrt-decomposition: 전처리 O(N), 업데이트 쿼리 O(1), 합 쿼리 O(sqrt(N))
• Fenwick tree: 전처리 O(N), 쿼리당 O(logN)
• Segment tree: 전처리 O(N), 쿼리당 O(logN)
• 관련 문제
  • 아무 응용 없이 기본 오퍼레이션만 처리하는 문제들.
  • 구간 합 구하기 (N≤1,000,000, Q≤20,000)
  • 수열과 쿼리 22 (N≤100,000, Q≤100,000)
  • 수들의 합 (N≤1,000,000, Q≤1,000,000)
    • 기본 문제들중 가장 범위가 크다. 제한시간은 2초(파이썬은 8초) 이지만, Python으로 제출하면 세그먼트 트리로는 통과하기 쉽지 않고, 펜윅트리로는 5초정도에 통과된다.

• Segment tree with lazy propagation: 전처리 O(N), 쿼리당 O(logN)
• 2개의 펜윅 트리를 사용하는 방법: 전처리 O(N), 쿼리당 O(logN)
• 구간 업데이트가 필요하지만, 그 이후에 구간 쿼리가 아니라 포인트 쿼리만 필요한 경우에는 계차수열 트릭의 테크닉을 사용해서 단순 펜윅트리 하나로만 처리하는 것이 가장 빠르다.
• 속도는 포인트 업데이트 쿼리가 있는 경우와 마찬가지로 2개의 펜윅트리 > 비재귀 세그먼트 트리 > 재귀 세그먼트 트리 순으로 빠르게 동작한다.
• 관련 문제
  • 구간 합 구하기 2 (N≤1,000,000, Q≤20,000)

• [!!] 여지껏 이 테크닉에 대해서 적당한 네이밍을 찾지 못해서 항상 장황하게 표현하곤 했었는데, 계차수열이라는 용어가 여기에 딱 해당한다는 것을 이제야 알았다. 이제부터 그냥 계차수열 트릭 이라고 표현하겠다.
• 주어진 배열 A 에 대해서 인접한 값의 차이로 이루어진 배열 B[i] = A[i] - A[i-1]를 만들어 볼 수 있다.
  • (이게 계차수열이다)
• 이렇게 변환한다면, A[i]의 값은 A[0]+(A[1]-A[0])+(A[2]-A[1])+…+(A[i]-A[i-1]) = B[0]+B[1]+…+B[i] 형태로 되어 B의 누적합으로 계산이 가능하다.
• 반면, A[l]부터 A[r]까지에 X를 더하는 업데이트는 A기준으로는 …, A[l-1], A[l]+X, A[l+1]+X, …, A[r]+X, A[r+1], …가 되어 r-l+1개의 원소의 값이 바뀌게 되지만, B기준으로는 (A[l]+X)-A[l-1], (A[l+1]+X)-(A[l]+X), …, (A[r]+X)-(A[r-1]+X), A[r+1]-(A[r]+X), …. = B[l]+X, B[l+1], …, B[r], B[r+1]-X, B[r+2], … 이런식이 되어, B[l]과 B[r+1]의 두개의 원소의 값만 바뀐다.
• 따라서, A대신 B를 저장해서 사용한다면, 구간 업데이트 + 포인트 쿼리를 포인트 업데이트 + 구간합 쿼리로 대신 처리할 수 있다. 따라서 lazy propagation을 사용하지 않고도 단순 펜윅트리를 이용해서 계산이 가능하다.
  • 한동안은 이것을 그때그때 구현해서 썼었는데 (사실 이렇게 처리하는 코드가 별로 복잡하지는 않다) 생각보다 이 테크닉이 자주 필요해져서 그냥 따로 라이브러리를 만들기로 했다.
    • teflib.fenwicktree#.FenwickTreeForRangeUpdatePointQuery
• 또한, 구간 업데이트가 다 끝난 뒤에, 포인트 쿼리들이 나오는 경우라면, 같은 방식으로, prefix sum을 이용해서 빠르게 처리할 수 있다. 구간 업데이트를 B에 대한 포인트 업데이트로 바꿔서 O(1)에 처리하고, 그 뒤에 O(n)으로 prefix sum을 구축하면, 포인트 쿼리들은 구간합 쿼리로 바꿔도 O(1)에 처리가 된다.
  • 사실 이 테크닉이 가장 효율적인 경우는 이 경우이다. 레이지 세그트리를 펜윅으로 바꾸더라도 시간복잡도 자체는 같은 O(logn)으로 상수값을 줄이는 효과밖에 없지만, 이 경우처럼 prefix sum으로 바꿀수 있다면 쿼리당 시간복잡도가 O(logn)에서 O(1)로 줄어든다
• 흔하지는 않지만, 만약 구간에 등차수열을 더하는 업데이트가 나오는 경우도, B기준으로 바꾸면 구간에 일정한 값을 더하는 업데이트로 변환 가능하다. 또한 여기에서 다시 B의 인접한 값의 차이로 이루어진 배열 C를 구성해서 사용한다면, C 기준으로는 포인트 업데이트로 변환이 되어서 문제 풀이가 더 쉬워지는 경우가 있다.
• 구현상 테크닉 중 하나는, 처음 트리를 초기화 할 때, B를 실제로 A[i]-A[i-1]로 계산해서 초기화하는 대신에, 그냥 모든 원소를 0으로 초기화해서 트리를 만드는 것이다. 그러면 트리에는 초기값을 제외하고 업데이트된 값들만 반영이 되므로, 포인트 쿼리에 대해서는 sum(B[0:i])에 원래 A[i]를 더한 값으로 계산해버리면 된다.
• 관련 문제
  • 광고 삽입 - (구간값으로 초기화 + 포인트 쿼리)를 (포인트값으로 초기화 + 구간합 쿼리)로 변환
  • 수열과 쿼리 21 - (구간 업데이트 + 포인트 쿼리)를 (포인트 업데이트 + 구간합 쿼리)로 변환
  • 하늘에서 떨어지는 1, 2, ..., R-L+1개의 별 - (등차수열 업데이트 + 포인트 쿼리)를 (구간 업데이트 + 구간합 쿼리)로 변환
  • 수열과 쿼리 39 - (등차수열 업데이트 + 구간 쿼리)를 (포인트 업데이트 + 구간 쿼리)로 변환. 구간 합 쿼리를 쓰지는 않지만 같은 유형이라서 포함했다

• Order Statistic Tree 참고

[to be filled..]

• XOR 연산은 합연산 만큼이나 다루기 쉬운 연산이다.
• 교환법칙은 기본으로 성립하고, 역연산이 존재하므로 누적합이나 펜윅트리 등, 구간 합에서 사용했던 방법들을 그대로 사용할 수 있다.
  • 인접한 원소간의 차이값으로 배열을 만드는 테크닉을 똑같이 적용해서, 구간 업데이트/포인트 쿼리를 포인트 업데이트/구간 쿼리로 변환해서 lazy propagation 없이 사용하는 것도 가능하다.
  • 구간 업데이트/구간 쿼리 문제를 lazy propagation 없이 Fenwick Tree 두개를 이용해서 구현하는 테크닉도 적용 가능하다.
    • 이것에 대해서 따로 설명된 자료는 아직 찾아보지 못했다. 그냥 구간합에서 사용하는 방법을 그대로 적용한다고 생각하면 되긴 하는데.. 좀더 쉬운 방법으로 설명이 가능할것 같은데 생각중이다.
    • 이렇게 구간 합과 같은 방식으로 구현하면, range update를 처리하는 데에 실제로는 펜윅트리 update 연산이 최대 4번까지 필요하고, range query도 마찬가지로 최대 4번의 펜윅트리 query 연산이 필요하다.
    • 그러나 조금 다른 방식으로 펜윅트리 두개를 사용하면 각각 2번씩의 연산만으로 처리할 수 있는 것 같다. https://www.acmicpc.net/source/13676152을 보고 발견한 방식인데, 아직 이해를 정확히 못했다..
• 처음에는 따로 만들 생각이 없었지만, 구간 xor을 요구하는 문제가 나름 있어서, teflib에 teflib.fenwicktree.XorFenwickTree를 추가로 만들었다. 구현은 그냥 FenwickTree에서 +와 -를 ^로 바꾼 것 외에는 동일하다.
  • 구간 합의 경우는 구간 업데이트/구간 쿼리 문제를 해결하는 teflib.fenwicktree.RangeUpdatableFenwickTree 도 만들었었지만, xor 버전의 구현체는 teflib에 추가하지는 않았다. 구현할때는 그냥 구간 합과 동일하게 구현하면 되지만 구간 합에서 {…}*X 에 해당하는 부분을 X가 홀수이면 {…}, 짝수면 0이 되도록 바꾸어주면 된다.

• Generic Queries - 업데이트 없이 쿼리만 들어오는 문제.
• XOR - 구간 업데이트/포인트 쿼리
• XOR - 구간 업데이트/구간 쿼리

• 구간에서 구하는 값이 최솟값인 경우. 이런 구간 최솟값 쿼리만 RMQ 라는 이름으로 줄여서 부르는 경우가 많다.
• min 함수의 특징은 역원이 없다는 특징 외에도, 구간내의 값을 중복해서 계산해도 결과가 동일하다는 특징이 있다.
  • min(a,b,c) = min(a,b,b,c) = min(min(a,b),min(b,c)) 이런게 가능.
• https://cp-algorithms.com/sequences/rmq.html 에 사용가능한 다양한 풀이법들이 시간복잡도와 구현난이도를 갖고 정리가 되어 있다.

• Sqrt-decomposition: 전처리 O(N), 쿼리당 O(sqrt(N))
• Segment tree: 전처리 O(N), 쿼리당 O(logN)
• Fenwick tree: 전처리 O(NlogN), 쿼리당 O(logN)
  • https://cp-algorithms.com/sequences/rmq.html에서는 [1, R]의 구간밖에 처리하지 못하는 것이 단점으로 적혀있다. 역연산이 없으니 일반적인 방식으로는 임의의 구간에 대해서 처리가 불가능 한 것이 맞지만, Fenwick tree 두개를 사용해서 RMQ를 처리하는 방법이 존재한다. (링크), (링크2). Segment tree를 쓰는것보다 실제 수행시간이 더 빠르다고 한다
• 관련 문제
  • 수열과 쿼리 17 (N≤100,000, Q≤100,000)

• Sparse Table: 전처리 O(NlogN), 쿼리당 O(1)
• Sqrt Tree: 전처리 O(NloglogN), 쿼리당 O(1)
• DisjointSet (Arpa's trick): 전처리 O(N*α(N)), 쿼리당 O(α(N)) - 오프라인 쿼리에서만 가능.
  • 사실상 α(N)은 상수라고 봐도 무방하다. 그러면 전처리 O(N), 쿼리당 O(1) 이 된다.
  • 자세한 방법은 여기 참고
• Cartesian Tree: 전처리 O(N), 쿼리당 O(1)
• 관련 문제
  • 최솟값

• 세그먼트 트리를 이용해서 쿼리당 O(logn)에 계산 가능하다. 일명 '금광세그'.
  • 2014년 KOI 중등부에 출제되었던 '금광'이라는 문제가 이 기법을 필요로 하는 바람에 급격히 유명해졌고, 금광세그라는 별칭을 얻게 되었다. 한국인들 사이에서는 유독 잘 알려져있는 테크닉이라고도 한다. 참고로 당시 KOI에서는 이 문제를 만점받은 사람이 아무도 없었다고 한다.
• 떠올리기 쉬운 테크닉은 아니지만, 애초에 전체 배열에서 최대 부분합을 구하는 문제가 원래 분할정복으로도 풀리는 문제라는 것을 기억하면, 그때에 구간을 머지하는데 사용했던 방법을 여기에서 그대로 사용할 수 있다는 것을 알 수 있다.
  • 전체 배열에 대해서 구할 때는 O(n)의 카데인 알고리즘이, O(nlogn)의 분할정복보다 빠르기는 하다.
• 각 구간에 대해서, (가장 왼쪽 값을 포함하는 최대부분합, 가장 오른쪽 값을 포함하는 최대부분합, 최대부분합, 전체합)을 갖고 있으면, 합쳐진 구간에 대해서도 저 값을 O(1)에 갱신할 수 있다. 자세히는 stonejjun 참고
• 두 구간에 대한 값으로부터 합쳐진 구간의 값을 계산하는 함수는, 교환법칙이 성립하지 않는다. 사용하는 기본 세그먼트 트리 코드가 교환법칙이 성립하지 않는 함수에 대해서도 동작하는지 확인해보자.
• 코드는 이런 식이다

  • def merge(l, r):
        l_lmax, l_rmax, l_max, l_all = l
        r_lmax, r_rmax, r_max, r_all = r
        return (max(l_lmax, l_all + r_lmax), max(r_rmax, l_rmax + r_all),
                max(l_max, r_max, l_rmax + r_lmax), l_all + r_all)
                
    segtree = SegmentTree(((x,) * 4 for x in arr), merge)            
    answer = segtree.query(beg, end)[2]

• 관련 문제
  • 연속합과 쿼리 : 업데이트 없이 쿼리만 있는 경우
  • 구간 합 최대? 2 : 업데이트와 쿼리가 둘다 있는 경우
  • 금광 : 금광세그라는 이름의 유래가 되는 문제라서 추가해 두긴 했지만, 금광세그 외에도 다양한 기법이 추가로 필요한 문제이다..

• '구간 내에서 X보다 작은 수의 갯수'를 묻는 쿼리이다. '구간 내의 원소들을 정렬했을때 X의 순위'도 결국 동일한 질문이다.
  • '구간 내에서 X보다 큰 수의 갯수'도 동일한 질문이다. {구간 내의 원소의 갯수} - {구간 내에서 X보다 작은 수의 갯수} - {구간 내에서 X의 갯수} 로 구하면 된다.
  • '구간 내에서 A와 B사이에 있는(A보다 크고 B보다 작은) 수의 갯수'도 마찬가지. {구간 내에서 B보다 작은 수의 갯수} - {구간 내에서 A보다 작은 수의 갯수} - {구간 내에서 A의 갯수}로 계산가능하다.
• 구간에 대한 쿼리가 아니라면, 정렬 후에 바이너리 서치를 써서 풀 수 있고, 원소의 삽입, 삭제도 일어난다면 Order Statistic Tree를 써서 풀어야 하는 문제이다.
• 이 기본 아이디어는 구간에 대한 쿼리에도 비슷하게 확장된다. 정렬 후에 바이너리 서치를 써서 푸는 것은 머지소트 트리로 확장되고, Order Statistic Tree를 쓰는 것은 Persistent Segment Tree 를 쓰는 방법으로 확장된다.
• 자세한 것은 아래에 쓰고 먼저 요약하면
  • 업데이트가 있으면
    • bbst를 노드로 갖는 세그먼트 트리를 사용하는 방법이 있긴 한데. 쉽지 않다. 구현 안해봄..
  • 업데이트가 없으면
    • 머지소트 트리 : O(nlogn + qlog^2(n))
    • Persistent Segment Tree : O((n+q)logm)
    • 시간 복잡도상으로는 PST쪽이 우수하지만, 일반적으로 문제에서 주어지는 n의 범위에서는 머지소트 트리가 더 빠른 경우가 많다.
  • 오프라인 쿼리로 처리가 가능하면
    • 오프라인 쿼리 + Order Statistic Tree: O((n+q)log(n+q))
    • 역시 시간 복잡도상으로는 PST랑 비슷한 것 같지만, 가장 빠르다.

• 머지소트 트리는 각 노드가 노드 범위 안의 원소들을 정렬된 상태로 저장하고 있는 세그먼트 트리를 의미한다. 이렇게 만들어도 메모리가 O(nlogn)이 된다는 것은 조금 생각하면 알 수 있다.
• 세그먼트 트리 기반이므로, 쿼리 구간은 O(logn)개의 노드로 나뉘어진다. 각 노드는 길이가 O(n)인 정렬된 리스트를 갖고 있다. 각 노드에 대해서 바이너리 서치를 적용하면 O(logn)에 x보다 작은 수의 갯수를 구할 수 있다. 구간 내에 모든 노드에 대해서 이것을 구하고 모두 더하면 쿼리 구간 안에서 x보다 작은 수의 갯수가 나온다.
• O(logn)개의 구간에서 O(logn)의 바이너리 서치를 해야 하므로 총 O(logn*logn) 에 쿼리를 처리할 수 있다.
• 세그먼트 트리를 활용하는 다른 문제들과는 다르게, 노드가 갖고 있는 값을 합치는 것과 동일한 함수로 구간의 대표값을 구한 후, 거기서 쿼리의 결과를 얻는 것이 불가능하다. 따라서 Teferi library의 SegmentTree 로는 구현이 안된다
  • 뭐 이경우는 SegmentTree에서 쿼리를 처리할 때의 노드값의 결합 방식을 정의하는 함수를 하나 더 추가로 받는 식으로 확장하면 처리가 가능하기는 하지만, 그냥 새로 클래스를 만들어서 쓰는것으로 처리했다
• cp-algorithms 에 나오는 Fractional Cascading 방법을 사용하면 O(log^2(n))이 아닌, O(logn)으로 줄이는 것도 가능하다고 하다. 그러나 "Fractional cascading is in fact slow?" 글에 따르면, 실질적으로는 더 느려졌다고 한다.
  • Fractional cascading 사용한 머지소트트리 (재귀) > 일반 머지소트 트리(재귀) > 일반 머지소트 트리(비재귀) 순서로 시간이 많이 걸렸다고 한다.
  • cpp기준이라서 python에서는 또 다를 수도 있긴 한데.. 구현은 귀찮아서 안해봤다.
• 실제 구현할때는, 두개의 정렬된 리스트를 정렬된 상태로 합치는 merge 연산을 구현해야 하는데, heapq.merge를 사용하거나, 직접 구현하는 방법도 있지만, 그냥 리스트 두개를 이어붙인 다음 내장 sort를 돌리는 방법이 효과적이다. merge는 O(n)인데 sort는 O(nlogn)이라 더 느릴것 같지만, 파이썬의 sort알고리즘인 timsort는 이런 형태의 데이터를 정렬하는 것을 거의 O(n)에 처리한다. 그래서 그냥 sort를 쓰는것이 낫다.

• PST를 쓰면, 세그먼트 트리에 k번 업데이트가 일어난 뒤에도, 그전 i번째 업데이트까지만 이루어진 상태를 기준으로 하는 쿼리를 처리할 수 있다.
• 따라서 Order Statistic Tree를 PST 형태로 만들면, i번째 원소까지만 추가되었을때의 rank, 다시 말하면 A[0:i] 중에서 k보다 작은 수의 갯수를 구할 수 있다. rank(A[i:j], k)는 rank(A[0:j], k) - rank(A[0:i-1], k) 로 쉽게 구할 수 있다.
• Order Statistic Tree를 기반으로 만든 것이라서, max(A)에도 복잡도가 영향을 받기는 한다. max(A) = m이라고 하자
  • PST는 다이나믹 세그먼트 트리를 기반으로 구현되므로 좌표 압축이 필수는 아니다. m값이 시간복잡도에 포함되는 경우에는 항상 log값이 씌워진 채로 붙게 되므로 m을 줄이는 것이 큰 차이를 주지는 않는다.. 그러나 m이 n보다 너무 크다면 좌표압축을 해서 줄일 수 있다. 이 경우에는 k들도 포함해서 좌표 압축을 해야 한다. 그러면 m을 n+q 로 바꿀수 있다.
• 공간복잡도는 O(nlogm)이 된다. PST를 구축하는데 걸리는 시간도 O(nlogm)이다. 이것은 머지소트트리의 O(nlogn)보다는 느리거나 별 차이 없다.
• 하지만 한 개의 쿼리를 처리하는 것이 O(logm)에 가능하다. 이는 머지소트 트리의 O(log^2(n))보다 효율적이다.
• 이렇게 보면, 머지소트트리를 쓰는 것이 의미가 없어 보이는데.. Python으로 실제로 구현했을 때는 머지소트 트리가 더 빠르게 동작했다.. PST를 쓰기 위해서는 top-down 형식으로 세그먼트 트리를 만들어야만 하고, 기타 상수항의 크기에서 머지소트 트리가 오히려 빨리 돌아가는 듯 하다.
  • 수열과 쿼리 1 문제(n=10^5, m=10^9, q=10^5)를 기준으로, PST는 오랜 시간 공들인 최적화 끝에 4600ms정도에 통과되었고 (좌표압축까지 하면 4200ms정도), 머지소트 트리는 1600ms 정도에 통과되었다.
  • 서로 다른 수와 쿼리 2 문제 (n=10^6, m=10^6, q=10^6) 는 실질적으로 구간 rank 쿼리 문제인데, 입력값의 범위가 특이하게 큰 문제이다. cpp의 최적 솔루션도 1000ms 이상이 걸린다. 이정도 사이즈가 되면 PST가 속도가 더 빨라진다. PyPy로 제출했을 때 PST로는 8304ms, mergesort tree로는 12300ms에 통과되었다. (python3 으로는 당연히 TLE)

• 오프라인 쿼리를 적용할 수 있다면 Order Statistic Tree만으로 해결 가능하다.
• 위에서 말했듯 rank(A[i:j], k) = rank(A[0:j], k) - rank(A[0:i-1], k) 이므로, 쿼리를 정렬해놓고 Order Statistic Tree에 원소를 하나씩 추가하면서 rank(A[0:j], k)들을 구해두고 answer 배열에 계산한 값을 저장해서 출력하면 된다.
• 이 경우에는 원소를 하나씩 추가하는 데에 O(nlogn), 쿼리를 하나씩 처리하는 데에 O(logn), 총 O((n+q)logn) 이면 해결된다.
  • SegmentTree 기반으로 처리하려면 좌표 압축이 필요하므로 O((n+q)log(n+q)) 시간이 추가로 들어서 O((n+q)log(n+q))가 된다.
  • 쿼리를 비교 기반으로 정렬한다면 O(qlogq)의 시간도 추가로 필요하다.
• 그리고 같은 로그 복잡도라도, PST 구현체에 비해서 상수값이 훨씬 작으므로, 실제 걸리는 시간도 우수하다
• 생각을 전환해서 다른 방식으로 오프라인 쿼리를 정렬하는 방법도 있다. A[x]=y 를 2차원 공간 상의 (x,y)라는 점으로 생각해보자. 위에서 설명한 방법은 x축 방향으로 스위핑을 하면서 푸는것과 동일하다. 이것을 바꿔서 y축 방향으로 스위핑을 한다고 생각해보자.
  • 이러면, 각 쿼리를 k값을 기준으로 정렬하고, 배열도 정렬한 뒤에, Order Statistic Tree에 원소를 하나씩 추가하면서 각 쿼리마다 Order Statistic Tree에서 [i, j] 사이에 있는 원소의 갯수를 리턴하면 된다.
    • 실질적으로는 k값들과 배열 값들을 같이 모아서 함께 정렬해야 할 것이다.
  • 배열을 정렬하는 과정이 추가되지만, Order Statistic Tree의 값의 범위가 0~N이므로 좌표 압축은 필요가 없어진다.
  • 결국 시간 복잡도는 동일하게 O((n+q)log(n+q)).
  • 이쪽은 구현해보지는 않아서 어떤쪽이 실제로 더 빠르게 동작할지는 예측 불가.

• 수열과 쿼리 1 - 가장 기본적인 버전
• 수열과 쿼리 3 - 수열과 쿼리 1과 다른 조건은 똑같지만, 오프라인 쿼리를 막아놓았다..
• 수열과 쿼리 1.5 - 업데이트도 처리해야 하는 버전

• '구간내에서 k번째로 작은 원소'를 찾는 쿼리이다.
  • k=1 일 때는 앞에서 설명했던 구간 최솟값 쿼리로 더 쉽게 처리 가능하다.
• 세줄 요약하면,
  • PST를 이용하는 방법은 시간복잡도가 O((n+q)logn)으로 가장 우수하지만 일반적인 n,q의 범위에서는 실제 속도는 느리다.
  • 머지소트 트리 + 바이너리서치 방법은 시간복잡도가 O(nlogn + qlog^3(n))으로 느리지만, PST보다 빠르게 동작하고, 가장 널리 알려져있는 방법이다
  • 인덱스를 가지고 머지소트트리를 만드는 방법은, 시간복잡도가 O(nlogn + qlog^2(n)) 으로 PST보다는 느리지만, 실질적으로는 가장 빨리 동작한다.
  • 이상은 모두 업데이트가 없을때 사용 가능한 방법. 업데이트가 있을 때 어떻게 할지는 찾아보지도 않았고 생각도 안해봤다.
• Persistent Segment Tree를 이용 - 쿼리당 O(logn)
  • 구간 Rank 쿼리와 비슷한 방식으로 Order Statistic Tree를 PST 형태로 만든다. Order Statistic Tree에서 kth elem을 찾는 방법은, left subtree의 합을 구하고 k값과 비교해서 left와 right중 한쪽으로 내려가게 되는데, left subtree의 합을 구하는 것을 {r개의 원소가 삽입된 상태의 합} - {l개의 원소가 삽입된 상태의 합}으로 바꿔서 처리해주면 계산 가능하다
  • 원래 PST의 값의 범위는 max(A)이지만, 좌표압축을 해서 n으로 줄일수 있으므로 O(logn)으로 적었다.
  • PST를 사용하는 여러 문제들을 오프라인 쿼리로 변환하여 PST 없이 풀 수 있는 것에 반해, 이 문제는 오프라인 쿼리로 풀기 어렵다. (적어도 나는 못떠올리겠고, 다른데서 찾을수도 없었다)
• 바이너리 서치를 이용하는 방법 - 쿼리당 O(log^3(n)) (또는 O(log^2(n))
  • '구간내에서 k번째로 작은 원소'를 바꿔 말하면 '구간내에서 x보다 작은 원소가 k-1개인 x'이다. 구간내에서 x보다 작은 원소가 몇개인지는 구간 Rank 쿼리를 이용해서 구할 수 있으므로, 바이너리 서치를 통해서 x값을 구하면 된다.
  • '구간내에서 k번째로 작은 원소'는 머지소트 트리를 이용해서 O(log^2(n))에 구할 수 있다. O(logn)개의 원소에 대해서 이 연산을 수행해야 하므로 시간 복잡도가 O(log^3(n))이 된다. 만약, 실제속도가 더 느리기는 하지만, '구간내에서 k번째로 작은 원소'를 Fractional cascading을 써서 O(logn)에 구한다면, k번째 원소를 구하는 시간도 O(log^2(n))이 되기는 한다.
  • PST에 비해서 시간 복잡도가 log^2(n) 배나 더 크지만, 실제로는 이게 더 빨리 돌아간다 ㄷㄷ
• 인덱스를 갖고서 머지소트트리를 구축 - 쿼리당 O(log^2(n))
  • cp-algorithm에도 소개되어 있지 않고, 다른 블로그들에서도 찾기 힘든 방법이다. k번째 수 문제의 정답 코드들을 읽어보다가 알게된 방법이다. 나중에 geeks for geeks에서 풀어 쓴 설명을 찾을 수 있었다.
  • (값,인덱스) 튜플들을 만들어서 값을 기준으로 정렬하고, 그렇게 정렬된 배열에서 인덱스만 뽑아서 머지소트트리를 만든다.
  • 이렇게 만들어진 트리의 성질은.
    • 어떤 노드의 left child에 저장된 인덱스에 해당되는 값들은 right child에 저장된 인덱스에 해당되는 값들보다 작다
    • 각 child의 인덱스들은 정렬된 상태이다
  • 따라서 루트에서 출발해서, left child에서 l~r사이에 있는 인덱스의 갯수가 k보다 작으면 left child로, 아니면 right child로 내려가는 식으로 l~r 범위안의 k번째 수의 인덱스를 찾을수 있다.
  • 각 노드에서 O(logn)의 바이너리 서치를 수행해야하고, 그것을 수행하는 노드의 갯수가 O(logn)개이므로 시간복잡도가 O(log^2(n))이다
• 코드는 k번째 수 를 참고

• 그 외의 문제들.
• 대표값을 구해놓은 구간에서 원소가 한개 추가 또는 삭제되었을때, 새 대표값을 쉽게 구할 수 있는 경우
  • f(a_l,a_l+1, …,a_r-1, a_r) = add(f(a_l, a_l+1, …, a_r-1), a_r) = del(f(a_l,a_l+1, …, a_r-1, a_r, a_r+1), a_r+1) 과 같은 add, del 연산이 존재하는 경우이다.
  • 업데이트가 없고, 쿼리를 오프라인으로 처리가능하다면 Mo's algorithm을 사용해서 O( (n+q)sqrt(n))으로 풀 수 있다.
  • 시간 복잡도가 훌륭한편은 아니다. 다른 방법이 사용 불가능할때의 최후의 수단으로 생각하자..
    • 예를 들어 f(a_l,a_l+1, …,a_r-1, a_r) = add(f(a_l, a_l+1, …, a_m), f(a_m+1, …, a_r-1, a_r)) 이 되는 add 연산이 존재한다면, 세그먼트 트리로 더 빠르게 계산이 가능하다.

[To be Filled]

• O(n)시간에 구축하면, 구간합을 O(1)에 구할 수 있게 해준다.
• 구현할 때에, prefix_sum을 a[0]부터 시작하도록 할 수도 있고, 0부터 시작하도록 할 수도 있다.
  • prefix_sum을 a[0]부터 시작하도록 하면, a[0]+a[1]+…+a[i] == prefix_sum[i] 가 되어서 정말로 누적합만 구할때에는 직관성이 높지만, 구간합 a[i]+a[i+1]+…+a[j]을 prefix_sum[j] - prefix_sum[i-1] 로 처리할때에는, i가 0인 경우를 따로 처리해야 해서 불편하다
  • 그래서 0부터 시작하는 방법을 사용하자. prefix_sum[i] = a[0]+a[1]+…+a[i-1] 로 저장한다. a[i]+a[i+1]+…+a[j]은 prefix_sum[j+1] - prefix_sum[i]가 된다. 어색해보이지만 sum(a[i:j+1]) 이라고 생각하면 자연스럽다.
• itertools.accumulate를 쓰는 방법과 assignment expression + list comprehension 조합으로 쓰는 방법이 둘다 가능하지만, 단순히 더하기 이상의 오퍼레이션이 들어갈 경우를 생각하면 (모듈러를 취한다든가) 후자가 더 유연하다. 속도도 후자가 조금 빠르다. 후자로 사용하자.

  • prefix_sum = list(itertools.accumulate(a, initial=0))

    이것 대신에

  • v = 0
    prefix_sum = [v] + [v := v + x for x in a]

    이것을 쓰자

• 위에서도 설명했지만 동작 원리는 크기가 2^k인 구간들에 대해서 대푯값을 유지해서, 임의의 구간에 대한 대푯값을, 미리 계산된 구간들의 대푯값을 조합해서 계산하는 방식이다.
• 크기가 n인 임의의 구간은 O(logn)개의 미리 계산된 구간들로 나눌 수 있다. 그래서 O(logn)개의 대푯값을 조합해서 계산하면 되고, 그 조합하는 연산의 복잡도가 O(T)라면 O(Tlogn)에 구간의 대푯값을 구할수 있다.
  • 대부분의 경우 구간을 조합하는 것은 O(1)이 걸려서, 구간 쿼리를 O(logn)에 처리하게 되
• 또, 특정한 인덱스를 포함하는 구간의 갯수도 O(logn)개 이다. 그래서 값을 한개 업데이트 하면, 그것을 포함하는 구간 O(logn)개를 업데이트해줘야 한다. 구간 한개를 업데이트하는데 O(T')이라면, 결국 값 업데이트 한개를 완전히 처리하는데에는 O(T'logn)이 걸린다.
• 재귀 함수를 이용하는 top-down 형태의 구현과, 비재귀로 동작하는 bottom-up 형태의 구현이 있다.
• bottom-up 형태의 구현은, 재귀 함수 호출이 없는 만큼 많이 빠르게 동작하고, 메모리도 정확하게 2*n개의 공간만을 차지한다.
• 비재귀로 구현하는 방법을 검색하면 여러 블로그 글이 있지만, 최초 출처는 codeforce 이고, 이곳의 설명이 가장 풍부하다 ⇒ https://www.acmicpc.net/blog/view/117 여기에도 한글로 매우 잘 설명되어있다!
  • 속도 면에서는 비재귀 구현이 훨씬 빠르다.
  • 메모리도 비재귀 구현이 적게 먹는다. 정확하게 2*n 크기의 배열로 동작한다.
  • 가장 큰 단점은 동작 방식이 직관적이지 않다는 점. 직관적이지 않은 정도가 아니라 꽤 생각을 해서 이해해 보려해도 어렵다. 크기가 2^k일때에는 전체 구간이 하나의 루트노드 아래에 있는 트리로 구성되어서 재귀방식과 같은 형태의 구조를 갖고 이해도 쉽다. 근데, 그렇지 않는 경우에는 전체구간이 여러개의 풀 바이너리트리들의 포레스트로 구성되는데, 이 경우에는 업데이트와 쿼리 코드가 동작하는 방식이 이해하기 쉽지 않다. 원문에서도 명쾌한 설명보다는 예시를 들어주면서 이렇게해서 잘 된다는 식이다..
  • 이렇게 때문에 실수하기 쉬운 점은, tree[1]이 최상위 노드이긴 하지만, tree[1]에 저장되는 값이 전체 구간의 대푯값은 아니다. 재귀 방식의 세그먼트 트리에서는, 전체 구간의 대푯값을 얻으려면 바로 루트 노드에 저장된 값을 가져오면 되지만, 비재귀에서는 이경우에도 쿼리 함수를 돌려서 O(logn)의 시간으로 가져와야 한다. 이것이 싫다면 길이를 2^k 로 맞춰서 트리를 구축하면, 이때는 tree[1]에 전체 구간의 대푯값이 저장된다. (이것을 필요로 하는 문제로 금광이 있다)
  • 동작 방법을 이해하기 힘들다보니, 복잡한 기능을 추가하기가 어렵다. 원 블로그에는 lazy propagation을 적용하는 방법도 설명되어 있으나, 이해가 어렵다보니, 비재귀 구현을 소개하는 대부분의 블로그에서는 그냥 lazy propagation이 필요한 경우에는 재귀 버전으로 구현하기를 추천하고 있다.
    • 좀 쉽게 접근하는 방법은, 그냥 사이즈를 2^k로 고정시키는 것이다. 그러면 구조가 좀 더 직관적이긴 하다.
  • 다른 단점으로 항등원이 없는 연산(예를들면 gcd)을 처리하기가 어렵다는 이야기도 있다. 이는 원래 구현(c언어)이 아랫처럼, res를 항등원으로 초기화 한 뒤에 업데이트를 하도록 되어있기 때문이다

    • int query(int l, int r) {  // sum on interval [l, r)
        int res = 0;
        for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
          if (l&1) res += t[l++];
          if (r&1) res += t[--r];
        }
        return res;
      }

    • 하지만 이건 간단하게 해결 가능하다. 아래처럼 res를 l번째 원소로 초기화하고, 거기에 [l+1,r] 구간을 추가 계산하면 된다.

      • int query(int l, int r) {  // sum on interval [l, r)
          int res = t[l + n];
          for (l += (n + 1), r += n; l < r; l >>= 1, r >>= 1) {
            if (l&1) res += t[l++];
            if (r&1) res += t[--r];
          }
          return res;
        }

• https://www.acmicpc.net/blog/view/117
• 구간 업데이트와 구간 쿼리를 둘다 O(logn)에 처리하고 싶다.
• 구간의 대푯값을 찾는데에 사용되는 함수 f와, 구간 값을 업데이트 하는데에 사용되는 함수 g가 같은 필요는 없다.
• 그러나 f가 f(f(a,b),c) = f(a,f(b,c)) 와 같이 결합조건을 만족해야 했던것처럼, g에도 조건이 필요하다.
• g가 어떤 파라메터 c를 x값에 적용하는 함수라고 하면, 노드 하나를 업데이트 하는 것은 x := g(x, c) 이렇게 쓸수 있을 것이다.
• 이제 '레이지 연산'을 적용하려면, 이것을 개별 노드가 아니라 구간에도 g를 적용할수 있어야 한다. 구간 내의 각 노드를 업데이트 한다음에 그것으로 만들어진 대푯값과 동일한 값을, 미리 계산된 구간에 대푯값에 업데이트를 적용해서 만들 수 있어야 한다.
  • 즉, f(g(x,c), g(y,c)) = g(f(x,y), c') 이 되어야 한다. c'은 c와, f(x,y)로부터 계산이 가능해야 한다. 보통은 c와 같거나 (예를 들면 f가 max, g가 add 일때), 구간의 크기값에만 영향을 받거나 한다 (예를 들면, f가 add, g도 add일때).
• 그리고 여러번의 업데이트 연산을 composition해서 하나의 연산으로 표현할수 있어야 한다.
  • 즉 g(g(x,c1),c2) = g(x, h(c1,c2))로 표현이 가능해야 한다.
• 그래서, 레이지 프로파게이션으로 문제를 풀려면, 문제에서 f와 리프노드에 대한 g는 주어질테고, 여기에 g를 구간에 대해서 일반화 시키는 것과 h를 어떻게 정의해주느냐를 찾으면 된다.
• 몇가지 예시를 들어보자.
  • add 업데이트, max 쿼리
    • f(x,y) = max(x,y)
    • g(x, c, size) = x + c
    • h(c1, c2) = c1 + c2
  • assignment 업데이트, sum 쿼리
    • f(x,y) = x + y
    • g(x, c, size) = c*size
    • h(c1, c2) = c2
  • 선형변환 업데이트 (x ⇒ ax+b), sum 쿼리
    • f(x,y) = x + y
    • g(x, (a,b), size) = a*x + b*size
    • h( (a1,b1), (a2,b2)) = (a1*b1, a2*b1+b2)

• teflib.segmenttree.LazySegmentTree

• 참고
  • 펜윅트리 (BOJ 블로그)
  • CP-algorithms.
• 1-based로 구현하는 방법과 0-based로 구현하는 방법이 있다. BOJ 블로그는 1-based, CP-algorithms는 0-based로 설명한다. 성능은 차이가 없고, 이해하기는 1-based가 조금더 편 하긴 하다. 밖으로 노출되는 api관점에서는 0-based가 좀 더 예뻐서, 개인적으로는 0-based로 짰다.
• 펜윅 트리는 세그먼트 트리와 비슷하지만, 세그먼트 트리가 조합해서 임의의 구간을 만들수 있도록 구간을 갖고 있는 반면에, 펜윅트리는 조합해서 [0,x]범위의 구간만 만들 수 있도록 구간을 갖고 있는다. 그래서 f([a,b]) 에 대한 값을 계산하려면 f의 역연산 g를 이용해서, g(f([0,b]), f([0,a-1]))과 같은 방법으로 계산해야 하고, 이러한 역연산 g가 존재하지 않는 경우에는 원칙적으로는 사용 불가능하다.
• 역연산이 정의되는 대표적인 연산은 더하기(구간합)이다. 이외에 xor 같은 경우에서도 사용이 가능하기는 하지만, 필요한 경우가 드물기 때문에, Teferi library의 펜윅트리 구현은 오직 구간합만 계산할수 있도록 만들었다.
  • 세그먼트 트리의 경우는 연산을 입력 인자로으로 받을 수 있게 해서 제너릭하게 만든것과는 대조된다.
• 펜윅트리는 세그트리보다 덜 유연한 대신에 속도가 빠르다. Python으로 구현해본 결과, 속도는 Fenwick tree > bottom-up segment tree > recursive segment-tree 순서로 빨랐다.
  • 10000개 정도의 쿼리에서는 속도 차이가 잘 안난다. 100,000개 정도 되면 속도 차이가 제법 난다.

• 펜윅 트리 두개를 잘 조합하면, 구간내의 원소들에 일정 수를 더하는 구간 업데이트와 구간 합을 모두 O(logn)에 처리할 수 있도록 만드는 것도 가능하다.
• 참고:
  • 펜윅 트리 200% 활용하기 (jh05013 블로그)
  • plzrun 블로그,
  • 같은 내용이긴 한데, plzrun 블로그쪽이 좀더 이해하기 쉽다.
• 속도는 세그먼트 트리에 lazy propagation을 적용한 것보다 더 빠르다.

• teflib.fenwicktree.RangeUpdatableFenwickTree

• 펜윅 트리 두개를 여차저차 잘 조합하면, 구간 최솟값도 처리할 수 있다. (https://tkql.tistory.com/69)

• 단순하게 쿼리 한번당 1번의 업데이트 or 구간합 연산이 사용되는 문제에 대해서만 비교

• 혼자서 생각해본 최적화 시도. 말이 안되는 아이디어는 아니었던것 같지만.. 결론만 요약하면 별 소용 없었다.. ㅜㅜ
• 펜윅 트리에서 [a,b)에 대한 구간합 query(a,b)는 query(0,b)-query(0,a-1) 로 계산되는 것은 기본적인 것이긴 한데.. query(0,b)과 query(0,a-1)을 각각 쪼개진 구간들의 합으로 구하게 되고, 이때 일부 구간은 겹치게 된다. 공통되는 구간을 더하고 빼는 작업을 하지 않도록 처리하면 더 빨라지지 않을까 하는 것이 기본 아이디어였다.
• 예를 들어 [57,59) 에 대한 구간합이라면, query(0,59) - query(0,57) 을 구하게 되는데, 이것은 (arr[58]+arr[57]+arr[55]+arr[47]+arr[31]) - (arr[56]+arr[55]+arr[47]+arr[31])로 계산하게 된다. 그런데 (arr[55]+arr[47]+arr[31]) 이후는 공통되므로 최적화하면 (arr[58]+arr[57] - arr[56]) 만으로 원하는 값을 구할수 있다는 것이다.
• 이 아이디어를 처음 구현한 방법은, l과 r중 더 큰쪽부터 계산하며 줄여나가다가, l==r이 되면 멈추는 것. 코드는 이런식이었다.

  • def query(self, beg: int, end: int) -> float:
            res = 0
            l, r = beg - 1, end - 1
            while l != r:
                if l < r:
                    res += self._tree[r]
                    r = (r & (r + 1)) - 1
                else:
                    res -= self._tree[l]
                    l = (l & (l + 1)) - 1
            return res

  • 그러나 충격적이게도 원래 방법보다 더 느려졌다.. 매 루프마다 추가된 것은 그냥 비교문밖에 없는데..;
• 그래서 다시 시도한 두번째 방법은, l==r이 되는 값을 미리 계산해서, 그 값이 될때까지 루프를 돌리는 것. 그 값은 아래 코드처럼 구할수 있다 (t값). t를 계산하는 비트연산식을 만드느라 고생하긴 했는데, 이게 가장 효율적인지는 모르겠다

• def query(self, beg: int, end: int) -> float:
          res = 0
          l, r = beg - 1, end - 1
          c = (beg ^ end).bit_length()
          t = (beg >> c) << c
          while r >= t:
              res += self._tree[r]
              r = (r & (r + 1)) - 1
          while l >= t:
              res -= self._tree[l]
              l = (l & (l + 1)) - 1
          return res

  • 그러나 이 방법 역시도 원래 방법보다 더 느려졌다.. 참내..