트 리 배열 (BIT) 초학

BIT (Binary Indexed Tree, BIT) 트 리 배열.트 리 배열 은 어떤 데이터 구조 입 니까?우 리 는 트 리 배열 이 동적 연속 과 조회 문 제 를 해결 하 는 데 쓰 인 다 는 것 을 알 고 있다.
데이터 구 조 는 n 개의 요 소 를 주 는 배열 a [1], a [2], a [3]... a [n] (아래 표 시 는 1 부터) 다음 과 같은 두 가지 조작 을 지원 합 니 다.
1. Add (x, y) 는 아래 에 x 로 표 시 된 a [x] 에 d 를 추가 하 는 것 을 말한다.템 플 릿 기본 값 은 update (x, y)
2. Query (L, R) 는 a [L] + a [L + 1] +... + a [R] 를 계산 하 는 것 이다.템 플 릿 은 기본적으로 read (x) 로 1 - x 의 합 을 구하 고 read (y) 는 1 - y 의 합 을 구하 고 read (y) - read (x - 1) 로 [x, y] 의 합 을 얻 습 니 다.
그래서 BIT 는 동태 적 인 연속 과 조회 문제 이다.
BIT 를 배우 기 전에 우 리 는 비트 연산 에 대해 일정한 인식 과 이 해 를 가 져 야 한다. 우 리 는 음수 에 있어 컴퓨터 에 서 는 그 패 치 형식 으로 저장 되 고 패 치 는 바로 그 원 코드 를 바탕 으로 기호 위치 에 변화 가 발생 해 서 는 안 된다 는 것 을 알 고 있 으 며 나머지 여러분 들 은 반 을 취하 여 얻 은 결 과 를 얻 을 수 있다.
이러한 연산 을 보 세 요. 예 를 들 어 7 의 이 진 은 00000111 이 라 고 표시 합 니 다. 그러면 - 7 의 이 진 은 1111001 이 고 그러면 00000111 & 1110001 의 결 과 는 0000001 입 니 다. 그래서...
이러한 연산 은 우리 에 게 7 의 이 진 표시 중 마지막 1 의 위 치 를 찾 아 주 었 고 이런 개념 이 생 겼 다.우 리 는 j - = j & (- j) 의 연산 을 진행 하면 111 - > 110 - > 100 - > 000 의 과정 임 을 알 수 있다.
이렇게 많아tree [] 로...   tree [i] 는 [i - (i & (- i) + 1, i] 이 구간 에서 a 배열 요소 의 합 을 나타 낸다.
예 를 들 어 우리 for (int i = 1; i < = n; i + +) a [i] = i;
a [1] ~ a [15] 원소 의 값 을 구하 고 싶 습 니 다.우 리 는 15 의 2 진법 이 (1111) 2 라 는 것 을 안다.
tree[15] = sum[15,15];
tree[14] = sum[13,14];
tree[12] = sum[9,12];
tree[8] = sum[1,8]; 
-> sum[1,15] = tree[1,8]+tree[9,12]+tree[13,14]+tree[15,15];
왜 이런 결과 일 까? 우 리 는 결점 i 에 있어 서 그 가 왼쪽 자 결점 이 라면 아버지의 노드 번 호 는 i + i & (- i) 라 는 것 을 알 게 되 었 다.
만약 에 i 가 오른쪽 자 결점 이 라면 아버지 노드 의 번 호 는 i - i & (- i) 이다.　　
증명 하기 어렵 지 않 습 니 다. 이 두 작업 의 시간 복잡 도 는 모두 O (nlogn) 입 니 다. 미리 처리 할 때 먼저 A 배열 과 C 배열 을 비 운 다음 에 n 번 update () 작업 을 수행 합 니 다. 전체적인 시간 복잡 도 는 nlogn 입 니 다.
- read (int pos) 에서 sum [1, pos] 를 구하 십시오.
- update (int pos, int v) a [pos] 를 v
주의해 야 할 것 은 업데이트 점 과 구간 을 조회 하고 아래 표 지 는 반드시 1 부터 시작 해 야 한 다 는 것 이다.
sum [l, r] 의 값 을 계산 하면 read (l) - read (r - 1) 로 이 루어 집 니 다.
다음은 read 의 두 가지 실현 방식 을 소개 합 니 다.
첫 번 째 는 while 로 썼어 요.

int read ( int pos )

{

    int ans = 0;

    while ( pos>0 )

    {

        ans+=tree[pos];

        pos-=pos&(-pos);

    }

    return ans;

}

두 번 째, for 로 쓴

int read ( int pos )

{

    int ans = 0;

    for ( int j = pos;j;j-=j&(-j) )

    {

        ans+=tree[j];

    }

}

 
그리고 update (int pos, int val) 의 쓰기 입 니 다.
while

void update( int pos,int val )

{

    while ( pos <= n )

    {

        tree[pos]+=val;

        pos+=pos&(-pos);

    }

}

두 번 째, for 쓰기

void update( int pos,int val )

{

    for ( int j = pos;j <= n;j+=j&(-j) )

    {

        tree[j]+=val;

    }

}

 
습관 에 따라 쓰 세 요. 사실 다 안 괜찮아 요.
 
 
 
 
데이터 구조 학습 노선:
트 리 배열 - > 더미 - > 선분 수 - > 밸 런 스 트 리 - > 나란히 쌓 기 - > 지구 화 선분 수 - > 트 리 세트 (- > 선인장)