BIT를 사용하여 증가하는 스퀘어의 수

EX의 경우 : 시퀀스가 1 3 2 4이되어 이제 증가하는 시퀀스의 수를 찾아야합니다.
O (nlog n) 솔루션에 O (n)와 비교해 볼 때 BIT 알고리즘에 대해 알게되었습니다.BIT를 사용하여 증가하는 스퀘어의 수

int read(int idx){ 
    int sum = 0; 
    while (idx > 0){ 
     sum += tree[idx]; 
     idx -= (idx & -idx); 
    } 
    return sum; 
}

를 읽으려면

void update(int idx ,int val){ 
    while (idx <= MaxVal){ 
     tree[idx] += val; 
     idx += (idx & -idx); 
    } 
}

을 따를
코드 내가 어떻게

출처

2014-11-06 user4213270

그래서 문제가 없음을 찾는 것입니다 (N 로그 n) 주어진 수열에서 증가하는 수의 수? 또한 '어떻게 그들이 BIT 알고리즘을 사용하고 있는지 이해할 수 없다'고 말할 때, 그들이 누구인지를 분명히해야합니다. – smac89

이진 트리의 read 함수가 반환됩니다, 색인 당신이 나에게 도움을 주시기 바랍니다 수 BIT 알고리즘을 사용하는 they 이해할 수있다 idx과 같거나 작은 값의 수

그래서, 삽입, n은 0에서 각 요소 하나 하나, 각 요소에 대해

(n은 요소 수입니다), 우리는이 현재 요소보다 작은 그 얼마나 많은 값을 알 필요가 , 그리고 이미 BIT에 추가되었습니다. 이 번호가 X라고 가정 때문에이 요소에 종료 증가 시퀀스의 개수가이 요소에서 종료하는 모든 서열을 계산 한 후, 2^X
을, 우리는 BIT에이 요소를 추가 할 필요

의사 코드 :

long result = 0; 
BIT tree = //initialize BIT tree 
for(int i = 0; i < n; i++){ 
    int number = tree.read(data[i] - 1);// Get the number of element that less than data[i]; 
    result += 1L<< number; 
    tree.update(data[i], 1); 

}

업데이트로

읽기 기능이 O를 시간 복잡도 (로그 n)이, 위 너 한테 시간 복잡도 O를 가지고

출처

2014-11-06 08:51:52

for 루프 이전에 비트 트리가 초기화되어 있습니까? BIT 트리를 초기화하는 방법을 설명 할 수 있습니까 – user4213270

@ user4213270 예, BIT를 초기화하는 방법은 이전에 초기화 되었습니까? 특별한 것은 없으며 빈 BIT를 만듭니다. –

BIT를 사용하여 증가하는 스퀘어의 수

답변

관련 문제