뒤집기 동전의 비트 작동

Question

이 코드를 이해하려고 노력했습니다. 세그먼트 트리 데이터 구조의 변형을 사용하고 있지만이 코드의 비트 연산을 이해할 수 없다고 생각합니다.

실제 문제는 N 코인있다이다 우리는 1 개 동작과

1. 범위에서 경화를 반전한다 1 명 질의 [A가 B]
2. 범위 헤드의 수를 찾아야 [A, B].

.

#define LEAVES (131072) 
#define MSB_V (0x80000000) 
#define MSB_P (31) 

int it[2 * LEAVES]; 
int A, B; //Query range 

void flip (int i, int min, int max) 
{ 
    if ((min > B) || (max <= A)) 
    { } 
    else if ((min >= A) && ((max-1) <= B)) 
    { it[i] ^= MSB_V; } 
    else 
    { 
     int l = 2 * i; 
     int r = l + 1; 
     int mid = (min + max)/2; 
     it[l] ^= it[i] & MSB_V; 
     it[r] ^= it[i] & MSB_V; 
     it[i] ^= MSB_V; 
     flip(l, min, mid); 
     flip(r, mid, max); 
     it[i] = (it[l] >> MSB_P ? mid - min - (it[l]^MSB_V) : it[l]) + 
       (it[r] >> MSB_P ? max - mid - (it[r]^MSB_V) : it[r]); 
    } 
} 

int count (int i, int min, int max) 
{ 
    int h; 
    if ((min > B) || (max <= A)) 
    { h = 0; } 
    else if ((min >= A) && ((max-1) <= B)) 
    { h = it[i] >> MSB_P ? max - min - (it[i]^MSB_V) : it[i]; } 
    else 
    { 
     int l = 2 * i; 
     int r = l + 1; 
     int mid = (min + max)/2; 
     it[l] ^= it[i] & MSB_V; 
     it[r] ^= it[i] & MSB_V; 
     it[i] ^= MSB_V; 
     it[i] = (it[l] >> MSB_P ? mid - min - (it[l]^MSB_V) : it[l]) + 
       (it[r] >> MSB_P ? max - mid - (it[r]^MSB_V) : it[r]); 
     h = count(l, min, mid) + count(r, mid, max); 
    } 
    return h; 
} 

누군가 나에게

Answer 1

it 완전한 이진 트리를 나타내는 모든 비트 연산 뒤에 논리 무엇인지에 대한 몇 가지 힌트를주지하시기 바랍니다 수있다; 노드 1은 루트이고 노드 k의 자식들은 2k와 2k + 1이다.

완전한 이진 트리의 잎은 동전입니다. 내부 노드는 일정한 방향 (낮은 31 비트)을 향한 동전의 수와 "플립 된"마커 (부호 비트)입니다. 반전 된 시장이 명확하면 낮은 31 비트가 노드의 하위 트리에서 헤드 업 동전의 수를 계산하고 반전 된 비트가 설정되면 꼬리 동전을 계산합니다.

여기 find 및 count 모두에 의해 사용되는 파라미터 협약 min 해당 노드로 표시되는 최저 인덱스, i 카운트 또는 대칭되는 노드로하고, max 가장 높은 인덱스이다. find과 count의 처음 두 테스트는 플립/카운트 범위 (A 및 B에 의해 정의 됨)가 노드 i의 범위에서 분리되거나 노드 범위를 포함하는지 확인합니다. 당신이 flip에서 볼 무엇

은 다음과 같습니다

은 [A, B] [최소, 최대]에서 분리 된이

• 경우에는 아무 것도 할 필요가 없습니다.
• [A, B]에 [최소, 최대]가 포함되어 있으면 뒤집힌 마커를 뒤집습니다.
• 그렇지 않은 경우 두 어린이에 flip을 실행하십시오. 일단 우리가 이것을하면, 여기에 불변성이 파멸됩니다. 두 아이 모두에 머리 수확 동전 수를 합산하여 문제를 해결하십시오. 당신이 count에서 볼 무엇

입니다 : [A, B] [최소, 최대]에서 분리 된 인 경우

이

• ,
• [A가 B] [분 포함되어있는 경우 0을 반환, max]이면,이 노드에서 카운트를 리턴한다.
• 그렇지 않으면 자녀 수를 더하십시오.