[트리] 펜윅 트리

펜윅 트리

• 누적합을 구한다.
• → 누적합을 이용하면 구간합도 구할 수 있음.
• 세그먼트 트리와 다르게 추가적인 공간(tree)이 필요없다.
• 만약 1~13번째 데이터의 구간합을 구하고 싶다면...
  • 8, 12, 13번 값을 알면됨.
    • 8 : 1~8까지의 값
    • 12 : 9~12까지의 값
    • 13 : 13의 값

LSB(Least Significant Bit) Index 정의하기

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
binary	0001	0010	0011	0100	-	-	-	-	-	-	-	-	-	-	-	-
LSB index	1	2	1	4	-	-	-	-	-	-	-	-	-	-	-	-
저 칸수만큼 나를 기준으로 왼쪽을 커버.

• LSB 구하기 : v&-v

  • 기존 이진수와 2의 보수를 and 연산하면 구할 수 있음.

• 업데이트 : 데이터 자신은 무조건 처음 업데이트 (오른쪽으로 감)

  • 자기자신에다가 LSB를 더함. -> 다음 이동 인덱스가 됨. (+업데이트)
  • 시간복잡도 $\log{N}$번만에 업데이트 가능.
    • 1~N까지 업데이트를 하는데, 보통 1+2+4+... 으로 감. = 1+2^1+2^2 = N 이 되어야한다는 소리. 그래서 $\log_{2}{N}$
    • 예시) 8 = 1+2+4(7)
      15 = 1+2+4+8(15)

• 쿼리, 조희 : 만약 13까지의 누적합을 구하고 싶을 때 (왼쪽으로 감)
  • 13에서 1빼서 12로 감. (13의 값 5더하기)
  • 12에서 4빼서 8로 감. (12의 값 20더하기)
  • 8에서 8빼서 0으로 감. 끝. (8의 값 39 더하기)
  • 시간복잡도 $\log{N}$번만에 조회 가능.