C 언어 트 리 배열 의 인 스 턴 스 상세 설명

C 언어 트 리 배열 의 인 스 턴 스 상세 설명
최근 에 트 리 배열 을 배 웠 는데 이 데이터 구조 가 신기 하 다 는 느낌 이 들 어 요 ^ ^
먼저 그녀의 상 수 는 선분 나무 보다 작고 그 다음 에 그녀의 실현 복잡 도 는 선분 나무 보다 훨씬 낮다.
그래서 그녀 를 익히 는 것 이 필요 하 다.
나무 모양 배열 의 기초 지식 과 원리 에 대해 인터넷 에서 한 무더기 검색 하면 나 는 군말 하지 않 고 나무 모양 배열 의 응용 에 대해 이야기 할 것 이다.
1. 단점 수정, 구간 화 구하 기

#define lowbit(x) (x&-x) //   x          y ,   lowbit(x) == 2^y 
void Update(int i,int v) //          
{
  while(i <= n)
  {
    c[i] += v ;
    i += lowbit(i) ;
  }
}

inline int Sum(int i)  //      
{
  int res = 0 ;
  while(i > 0)
  {
    res += c[i] ;
    i -= lowbit(i) ;
  }
  return res ;
}

2, 구간 수정, 단일 검색
여 기 는 차분 한 사상 을 써 야 한다.
차이 점 그룹 c [] 를 만 들 고 c [i] = a [i] - a [i - 1] (a [i] 는 원래 의 i 번 째 수 를 표시 합 니 다)
a [i] = (a [i] - a [i - 1]) + (a [i - 1] - a [i - 2]) +... + (a [2] - a [1]) + a [1]
         = c[i] + c[i-1] + ...... + c[2] + c[1]
그래서 단일 조회 가 구간 구 화 로 바 뀌 었 습 니 다.
그러면 구간 수정 은 어떻게 하나 요?
우 리 는 이런 예 를 본다.
a 1 3 4 5 7 10
c 1 2 1 1 2 3
우리 가 구간 [2, 4] 에 2 를 더 하면...
a 1 5 6 7 9 10
c 1 4 1 1 2 1
우 리 는 c [2] 와 c [5] 의 수치 만 바 뀌 었 다 는 것 을 알 수 있다. 사실 원리 도 매우 보고 싶다. 구간 내의 전후 원소 차 는 변 하지 않 고 (구간 의 첫 번 째 원소 와 앞의 원소 의 차이) 와 (구간 뒤의 첫 번 째 원소 와 구간 의 끝 원소 의 차이) 만 바 뀌 었 다.그래서 구간 수정 문 제 는 단점 수정 문제 로 바 뀌 었 다.

  for(int i=1;i<=n;i++)
  {
    a[i] = read() ;
    Update(i,a[i]-a[i-1]);
  } 
/*  int x=0,y=0;    //              （        ）
  for(int i=1;i<=n;i++)
  {
    if(i%2)
    {
      x = read() ;
      Update(i,x-y);
    }
    else
    {
      y = read() ;
      Update(i,y-x) ;
    }
  } */
  int ii ;
  int k,x,y;
  for(int i=1;i<=m;i++)
  {
    ii = read() ;
    if(ii == 1)
    {
      x = read() ; y = read() ; k = read() ;
      Update(x,k);
      Update(y+1,-k);
    }
    if(ii == 2)
    {
      x = read() ;
      printf("%d
",Sum(x));
    }
  }

(낙 곡 에 대응 하 는 템 플 릿 문제 P3374 와 P3368)
위 는 트 리 배열 의 가장 기본 적 인 두 가지 응용 으로 앞으로 더 깊이 공부 한 후에 업데이트 하 는 것 이다.
 궁금 한 점 이 있 으 시 면 메 시 지 를 남기 거나 본 사이트 지역사회 에 가서 토론 을 교류 하 세 요. 읽 어 주 셔 서 감사합니다. 도움 이 되 셨 으 면 좋 겠 습 니 다. 본 사이트 에 대한 지지 에 감 사 드 립 니 다!