선분 트 리 상세 설명 및 C+구현 코드

응용 장면
만약 에 이런 문제 가 있다 고 가정 하면 n 개의 수,m 번 의 조작 이 있 고 조작 은 특정한 수 를 수정 하거나 구간 의 값 을 조회 하 는 것 으로 나 뉜 다.
분석 해 보면 배열 요소 에 대한 수정 이 O(1)로 이 루어 질 수 있다 면 특정한 구간 값 을 구 하려 면 O(n)가 있어 야 이 루어 질 수 있 고 m 와 n 이 모두 큰 경우 이 복잡 도 는 받 아들 이기 어렵다.
우리 가 이전에 배 운 접두사 와 알고리즘 은 구간 의 구 화 문 제 를 해결 할 수 있 고 시간 복잡 도 는 O(1)이지 만 수정 작업 과 관련 되면 접두사 와 배열 은 모두 다시 계산 해 야 하 며 시간 복잡 도 역시 O(n)이다.
상기 두 가지 조작 을 동시에 고려 할 수 있 고 시간 복잡 도 를 낮 출 수 있 는 방법 은 없 습 니까?
이것 이 바로 우리 가 배 워 야 할 선분 나무 다!수정 과 조회 의 시간 복잡 도 를 모두 O(logn)로 낮 춥 니 다!!
알고리즘 사상
먼저 선분 나무 가 어떻게 생 겼 는 지 살 펴 보 자.
다음 배열 이 있 습 니 다.

우 리 는 그것 을 선분 나무 로 바 꾸 었 다.이렇게 생 겼 다.

1)잎 결점(녹색)은 모두 원수 조 원소 의 값 을 저장한다
2)각 부모 의 결산 점 은 두 개의 키 노드 의 값 과
3)각 부모 노드 는 구간 의 범 위 를 표시 하 며,위의 그림 의"1-2"는 1 에서 2 의 구간 을 표시 한다.
다음은 선분 나무 가 어떻게 조작 복잡 도 를 낮 추 는 지 살 펴 보 자!
조회 조작
예 를 들 어 우 리 는 2-5 구간 의 합 을 조회 해 야 한다.

재 귀적 사상 사용:
2~5 의 합
=2~3 의 합+4~5 의 합
=3+5+4~5 의 합
=3+5+11
=19
한 마디 로 선분 나무의 구분 을 따라 구간 을 나 누고 한 조각 만 더 넣 으 면 된다!
조작 을 수정 하 다
예 를 들 어 우 리 는 결점 2 의 값 을 3->5 로 바 꾸 려 면 선분 나 무 는 빨간색 부분 을 따라 하나씩 바 꾸 어야 한다.

수정 작업 이 든 조회 작업 이 든 시간 복잡 도 는 O(logn)입 니 다.
다음 단 계 는 선분 수 를 어떻게 실현 하 는 지 보 겠 습 니 다!
알고리즘 구현
우선 우 리 는 원시 배열 을 하나의 선분 트 리 로 만 든 다음 에 나 무 를 바탕 으로 조회 와 수정 작업 을 제공 해 야 한다.
세우다
위의 그림 을 살 펴 보면 우 리 는 선분 나무 가 완전 이 진 트 리 와 비슷 하 다 는 것 을 발견 했다.완전 이 진 트 리 의 성질 을 이용 하면 우 리 는 직접 하나의 배열 로 그것 을 저장 할 수 있다.

위의 그림 처럼 각 노드 에 번 호 를 표시 합 니 다.만약 에 뿌리 노드 번호 가 n 이 라면 왼쪽 트 리 번 호 는 2n 이 고 오른쪽 트 리 의 번 호 는 2n+1 입 니 다.
그래서 뿌리 노드 의 번 호 를 알 게 되면 우 리 는 왼쪽 과 오른쪽 나무의 뿌리 노드 를 신속하게 찾 을 수 있다.

void build(int root,int start,int end){
    if(start == end){
        tree[root] = num[start];
        return;
    }
    int leftroot = root * 2;//   
    int rightroot = root * 2 + 1;//   
    int mid = (start+end)/2;
    build(leftroot,start,mid);//       
    build(rightroot,mid+1,end);//       
    tree[root] = tree[leftroot] + tree[rightroot];//    =  +  
}

조회 하 다.

int query(int root,int start,int end,int l,int r){
    if(l<=start && r>= end){
        return tree[root];
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start+end)/2;
    int sum = 0;
    if(l<=mid){
        sum += query(leftroot,start,mid,l,r);
    }
    if(r>mid){
        sum += query(rightroot,mid+1,end,l,r);
    }
    return sum;
}

수정 하 다.

/**
*   [l,r]     ，   k 
* @param root
* @param start
* @param end
* @param l
* @param r
* @param k
*/
void update(int root,int start,int end,int l,int r,int k){
    if(start == end){
        tree[root] += k;
        return;
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start+end)/2;
    if(l<=mid){
        update(leftroot,start,mid,l,r,k);
    }
    if(r>mid){
        update(rightroot,mid+1,end,l,r,k);
    }
    tree[root] = tree[leftroot] + tree[rightroot];
}

！！！：구간 별로 원소 값 을 수정 하 는 복잡 도 를 고려 해 볼 까요?
주의사항:
1)우리 가 선분 트 리 를 실현 할 때 실제 저장 소 는 원시 배열 보다 클 것 이다.우 리 는 보통 tree 배열 의 길 이 를 원시 데이터 길이 의 3-4 배 로 한다.
2)본 고 는 단지 여러분 에 게 선분 나무의 실현 원 리 를 배우 게 하기 위해 서 입 니 다.실제 적 으로 우 리 는 원시 배열 의 start,end 를 구조 체 로 저장 할 수 있 습 니 다.이렇게 하면 더욱 간결 합 니 다.
총결산
여기 서 선분 트 리 에 대한 상세 한 설명 과 C++실현 에 관 한 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++실현 선분 트 리 내용 은 예전 의 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!