`IndexTree`

特点:

1)支持区间查询

2)没有线段树那么强,但是非常容易改成一维,二维,三维的结构

3)只指出单点更新(线段树可以实现范围更新)

ps:线段树的作用:1.add(L,R,10),某个区间同时加上10

2.update(L,R,7)某个区间同时变成7

3.求区间(L,R)的累加和

三分函数的时间复杂度都为O(logN)

例如数组{1,2,3,4,5,6,7,8}

index=1->管1

index=2->管1,2

index=3->管3

index=4->管1,2,3,4

index=5->管5

index=6->管5,6

index=7->管7

index=8->管1,2,3,4,5,6,7,8

规律一:当将index化为二进制表示的形式

如当index=8=01000

将最右边的1改为0并在末尾加上1后的二进制形式为index’=00001

则index=8时管的范围时index’到index–>即为1到8