하위 배열의 XOR 쿼리

1310. 하위 배열의 XOR 쿼리

난이도:중

주제: 배열, 비트 조작, 접두사 합계

양의 정수로 구성된 배열 arr이 제공됩니다. 쿼리[i] = [left_i, right_i].

인 배열 쿼리도 제공됩니다.

각 쿼리에 대해 왼쪽_i에서 오른쪽_i으로 요소의 XOR을 계산합니다(즉, arr[left_i] XOR arr[left_i 1] XOR ... XOR arr[right_i] ).

답변답변[i]이 i^번째 쿼리에 대한 답인 배열 답변을 반환합니다.

예 1:

• 입력: arr = [1,3,4,8], 쿼리 = [[0,1],[1,2],[0,3],[3,3]]
• 출력: [2,7,14,8]
• 설명: 배열 요소의 이진 표현은 다음과 같습니다.

  1 = 0001
  3 = 0011
  4 = 0100
  8 = 1000

쿼리의 XOR 값은 다음과 같습니다.

  [0,1] = 1 xor 3 = 2
  [1,2] = 3 xor 4 = 7
  [0,3] = 1 xor 3 xor 4 xor 8 = 14
  [3,3] = 8

예 2:

• 입력: arr = [4,8,2,10], 쿼리 = [[2,3],[1,3],[0,0],[0,3]]
• 출력: [8,0,4,4]

제약조건:

• 1 <= arr.length, query.length <= 3 * 10⁴
• 1 <= arr[i] <= 10⁹
• 쿼리[i].length == 2
• 0 <= 왼쪽_i <= 오른쪽_i < 길이

힌트:

1. x ^y ^x 의 결과는 무엇입니까?
2. XOR의 접두어 합계를 계산합니다.
3. 접두사 합계 값으로 쿼리를 처리합니다.

해결책:

접두사 XOR 기술을 사용할 수 있습니다. 작동 방식은 다음과 같습니다.

접근하다:

1. 접두사 XOR 배열: 접두사 XOR 배열을 계산합니다. 여기서 접두사[i]는 배열 시작부터 인덱스 i까지 모든 요소의 XOR을 나타냅니다. 이를 통해 일정한 시간에 모든 하위 배열의 XOR을 계산할 수 있습니다.

2. 하위 배열의 XOR:

   • 왼쪽 인덱스와 오른쪽 인덱스 간 요소의 XOR을 계산하려면 다음을 수행하세요.
     • 남은 경우> 0이면 접두어[오른쪽] ^ 접두어[왼쪽 - 1]로 왼쪽에서 오른쪽으로 XOR을 계산할 수 있습니다.
     • left == 0이면 결과는 단순히 접두사[right]입니다.

이를 통해 접두사 XOR 배열을 구성한 후 일정한 시간 내에 각 쿼리에 응답할 수 있습니다.

계획:

1. 접두사 XOR 배열을 만듭니다.
2. 각 쿼리에 대해 접두사 XOR 배열을 사용하여 [left_i, right_i] 범위에 대한 XOR을 계산합니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 1310. 하위 배열의 XOR 쿼리

  
  
  설명:




접두사 XOR 구성:


배열 접두사는 prefix[i]가 arr[0]부터 arr[i]까지 모든 요소의 XOR을 포함하도록 구성됩니다.
예를 들어 arr = [1, 3, 4, 8]인 경우 접두사 배열은 [1, 1^3, 1^3^4, 1^3^4^8] 또는 [1, 2입니다. , 6, 14].



질의 응답:


각 쿼리 [left, right]에 대해 다음을 사용하여 하위 배열 arr[left]와 arr[right]의 XOR을 계산합니다.



접두사[오른쪽] ^ 접두사[왼쪽 - 1] (왼쪽 > 0인 경우)

접두사[오른쪽](왼쪽인 경우 == 0)







  
  
  시간 복잡도:




접두사 배열 만들기: O(n), 여기서 n은 배열의 길이입니다.

쿼리 처리: O(q), 여기서 q는 쿼리 수입니다.

전체 시간 복잡도: O(n q), 이는 주어진 제약 조건에 효율적입니다.


이 접근 방식을 사용하면 최대 30,000개의 배열에서 최대 30,000개의 쿼리를 효율적으로 처리할 수 있습니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.


링크드인
깃허브



          

            
  

            
        
위 내용은 하위 배열의 XOR 쿼리의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!