【数据结构】树状数组笔记

前端之家收集整理的这篇文章主要介绍了【数据结构】树状数组笔记前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

树状数组(Binary Indexed Tree,BIT)

转自大牛柳婼 の bloghttps://www.liuchuo.net/archives/2268

  • 本质上是按照二分对数组进行分组,维护和查询都是O(lgn)的复杂度
  • 树状数组与线段树:树状数组和线段树很像,但能用树状数组解决的问题,基本上都能用线段树解决,而线段树能解决的树状数组不一定能解决。相比较而言,树状数组效率要高很多。
  • lowbit
    • lowbit = x & (-x)
    • lowbit(x)也可以理解为能整除x的最大的2的幂次
  • c[i]存放的是在i号之前(包括i号)lowbit(i)个整数的和(即:c[i]的覆盖长度是lowbit(i) )
  • 树状数组的下标必须从1开始

单点更新,区间查询

int getsum(int x)函数:返回前x个整数之和

  • 如果要求[x,y]之内的数的和,可以转换成getsum(y) – getsum(x – 1)来解决

void update(x,v)函数:将第x个数加上一个数v

经典应用:统计序列中在元素左边比该元素小的元素个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
#include <cstring>
const maxn 10010 ;
#define lowbit(i) ((i) & (-i))
maxn ;
void update , v {
< )
] ;
}
{
;
)
@H_319_404@ ;
;
}
main ( {
n ;
scanf ( "%d" & ;
i ++ {
;
;
printf "%d\n" x - ;
}
;

如果是求序列第k大的问题:

可以用二分法查询第一个满足getsum(i) >= k的i

4
5
6
7
8
9
10
11
findKthElement k {
l 1 r maxn mid ;
while < r {
mid + / 2 ;
if ( getsum >= K )
;
else
;
}
return l ;

如果给定一个二维整数矩阵A,求A[1][1]~A[x][y]这个子矩阵中所有元素之和,以及给单点A[x][y]加上整数v:

只需把getsum和update函数中的for循环改为两重

;
y {
{
j j {
;
}
}
}
{
;
{
)
;
}
;

区间更新,单点查询

  • 将getsum改为沿着i增大lowbit(i)的方向
  • 将update改为沿着i减小的lowbit(i)的方向
  • c[i]不再表示这段区间的元素之和,而是表示这段区间每个数被加了多少
  • int getsum(int x)返回第x个整数的值(就是从小块到大块累加一共被增加了多少)

{
sum 0 ;
)
] ;
sum ;

  • void update(int x,int v)是将前x个整数都加上v

{
)
;


  • 所以,~~i从x往后是从小块更新到大块c[i],i从x往前是累加前面的覆盖块的值~

1057. Stack (30)-PAT甲级真题(树状数组)

  • 求栈内所有元素的中位数:用排序查询方法会超时~~~用树状数组,即求第k = (s.size() + 1) / 2大的数。查询小于等于x的数的个数是否等于k的时候用二分法更快~

猜你在找的数据结构相关文章