모든 연산에서 배열 시작 부분에 요소를 추가하고 주어진 범위의 합계를 계산하는 방법은 무엇입니까?

Question

처음에 배열은 N(1<=N<=105)입니다. 당신은이 개 정수 l 및 r를 부여

(i) Operation 1 : Op1(l, r) 

:이 배열을 감안할 때, 당신은 작업의 2 종류가 수행해야합니다. (1 <= l <= r <= current size of the array). l과 r (둘 모두 포함) 사이의 인덱스를 가진 모든 요소의 합계를 반환해야합니다. 즉, 현재 배열에있는 요소가 a1, a2, a3 .... an 인 경우 다음을 반환해야합니다. sum : al + al+1 + al+2 ... + ar.

(ii) Operation 2 : Op2(x) 

단일 정수 x (|x| <= 109)이 제공됩니다. 이 요소를 배열의 시작 부분에 추가하십시오. 이 작업 후 x은 이제 a1이되고 old a1은 a2이됩니다. 배열의 크기가 1만큼 증가합니다.

나는 주어진 초기 배열로 세그먼트 트리를 만들었고 범위 합계를 계산할 수 있었지만 ... 어떻게 세그먼트 트리에 하나의 요소를 추가하고 그에 맞게 수정할 수 있습니까?

Answer 1

TREAP (Randomized Binary Search Tree)로 알려진 데이터 구조를 사용할 수 있습니다. -

먼저 읽기 배열 A의 :이 오프라인 알고리즘을 시도 cs.cornell.edu/Courses/cs312/2003sp/lectures/lec26.html

Answer 2

-이 링크를 treap에 대한 추가 정보를 원하시면 .

그런 다음 모든 쿼리에 읽을 그들을 저장하고 또한 지금은

K.

하자, 제 2 형 쿼리의 어떤을 계산 길이 K +의 길이 b를 새로운 배열을 생성 (A).

이제 b의 인덱스 1에서 시작하여 쿼리를 거꾸로 통과하면서 모든 유형 2 쿼리가 요소를 배열 b에 추가합니다.

이제 배열 b에 세그먼트 트리 또는 이진 인덱스 트리를 작성하십시오.

그럼 그냥 1

에 의해 C를 증가 쿼리의 목록을 통과하고 제 2 형의 각 쿼리에 대해 지금까지 발생 타입의 2 번 쿼리를 세고 0

로 초기화 변수 C를 사용하여

배열 1에 범위 1 ... r이있는 형식 1의 쿼리의 경우 배열 b의 범위는 (l + kc) ... (r + kc)에 해당합니다.

변환 된 범위에서이 쿼리에 응답하려면 위에 작성된 세그먼트 트리 또는 이진 인덱스 트리를 사용하십시오. 도움이 되었기를 바랍니다.