找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 5165|回复: 1
收起左侧

[面经总结] Binary Indexed Tree 介绍

[复制链接]

24

主题

9

精华

602

积分

超级会员

Rank: 4

积分
602
发表于 12-22-2014 06:52 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
csps介绍的点树参见[面经总结] 分享一种数据结构——点树! }" P: ?- g1 d
这里介绍的Binary Indexed Tree(BIT),参见《挑战程序设计竞赛》秋叶拓哉 p174
: e: B; E! u: Z$ F2 d. @3 h2 ]BIT的好处是数组的大小可以是插入的最大值,不需要用最接近的2^a空间。
% x6 D1 E$ _+ y( w1 g9 x6 IBIT和线段树的区别是减少了所有的右树。数组bit[0]不存储信息,bit【i】存储的区间是(i- (i & -i), i]。# G0 t0 g0 Z* s
比如bit[1]的区间是(0,1], bit[4]的区间是(0,4],bit[5]的区间是(4,5].$ c# n+ R. z( Y; L8 P5 S7 z
add用来加入数i, sum用来求(0,i]的数
2 |' @+ c5 C; ?" ?8 C: B1 U# X% C6 }java 代码如下:
; N0 k  K7 `$ I" t$ n3 D" a3 `0 Y+ S3 w/ L8 {8 s  E1 I( E) e
  1. class BIT {
    7 ~) x# Q; D9 ?
  2.         // interval [1,n]( x1 [$ t0 T% ^4 x
  3.         int[] bit;0 s* {0 L$ \" g8 W3 G
  4.         int n;
    6 n6 r! l0 ]* z7 O/ ^0 G
  5. ) [! ]1 h* r3 k
  6.         public BIT(int n) {/ l5 G* O, b/ b' Z! }; e% }
  7.                 this.n = n;
    & P8 g' u; g$ g& e# E
  8.                 bit = new int[n + 1];5 H5 M! i2 Q& Z* l$ m% B
  9.         }
    2 ~$ k) L; r3 S2 B' [" d" o1 T& T* a
  10. , g2 b( V/ I9 ]$ G' I
  11.         public void add(int i) {5 X, ]. u9 S4 C3 p' o, ]) q9 V  c
  12.                 while (i <= n) {
    # r) X. |6 d# N& K2 T$ C4 ]: c
  13.                         bit【i】 ++;
    7 Z  w. l( H% a* {9 ?$ ~$ p' a7 U
  14.                         i += i & -i;
    2 i8 t( V- D; m' q- `$ D" f1 O
  15.                 }
    , s/ z  p0 [* s4 A3 J% r
  16.         }
    ; Z1 K8 p% U7 D# {4 n7 F

  17. , }2 {# W$ m- J! Y4 n; e
  18.         public int sum(int i) {. a! U5 [" M  r- g3 n# C& C
  19.                 int s = 0;
    9 @8 G' H! S: P) ^
  20.                 while (i > 0) {
    / v) @) z( }- ^3 _4 ]
  21.                         s += bit【i】;9 p1 U3 W. e' R6 R) l* C  ?
  22.                         i -= i & -i;
    ) {; B& F: X+ _0 Y$ ?! `
  23.                 }
    & n' _( I: p% H& B+ J) `6 p' h
  24.                 return s;, t% A4 |4 I* \! u
  25.         }" D3 [5 e% j* c9 O. L; F) \. p
  26. }
复制代码
7 g8 ]! G5 D9 D6 J' ^3 D+ [2 ?

3 h( K+ E% W, a) H% Z3 B) E& n6 K% Z3 Y1 S' L1 Q
9 L" p$ Z/ `% ^1 w+ X; y
, L- \5 w( i5 T+ V) G7 x& J1 a% R. F- l

. \6 M' y8 _+ s1 n4 [9 U) M7 C, b
发表于 12-22-2014 07:37 PM | 显示全部楼层
我看是一个东西。。。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表