나는 일련의 숫자 A [0] ~ A [n-1]을가집니다.Gcd 및 업데이트 쿼리
가능한 쿼리는 2 개가 될 수 있습니다.
검색어 1 : gcd i j : 모든 번호의 gcd를 계산합니다. A [k] i < = k < = j.
쿼리 2 : 업데이트 i j : j를 A로 변경합니다.
예 :
gcd 2 4
gcd 1 5
update 2 3
gcd 2 4
update 4 1
gcd 3 6
가장 빠른 알고리즘은 무엇입니까?
좋은 질문,
첫 번째 아이디어는 세그먼트 트리를 사용하는 것입니다. 세그먼트 트리에 익숙하지 않은 분은 여기서는 매우 유용한 튜토리얼입니다. 각 노드에서 우리는 그 노드에 의해 커버되는 세그먼트에있는 숫자의 gcd를 유지할 수 있습니다. 따라서 각 업데이트 쿼리에 대한 노드의 로그 번호를 고려해야하며 두 번째 쿼리의 경우 루트 노드에 보관 된 값을 반환 할 수 있습니다. 각 노드에 대해 두 자식 값의 gcd를 계산해야하므로 업데이트 쿼리에는 O ((logn)^2) 시간이 필요하고 두 번째 쿼리에는 O (1) 시간이 필요합니다. https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/#Segment_Trees
나는 세그먼트 나무를 안다. 내가 호기심을 자극하게 한 이유는 이것에 대한 더 빠른 기법이 있다면 : P –
O (logn)보다 빠르다는 뜻은 O (1)입니까? 어쩌면 양자 컴퓨터 – Mamuka
가 정확히 무엇을 할 : 여기
세그먼트 나무에 대한 링크입니까? GC를 찾으세요? – Lrrr에는 두 가지 유형의 쿼리가 있습니다. 각 쿼리에 대해 해당 답변을 제공해야합니다. @AliAmiri –
스왑에는 확실한 O (1) 대답이 있습니다. temp = a [i], a [i] = a [j], a [j] = temp. 하지만 저는 현재 GCD를위한 가장 빠른 방법을 생각하고 있습니다. – Lrrr