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

原文

树状数组（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 {
< )
] ;
}
{
;
)
;
;
}
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的时候用二分法更快~

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 dio@foxmail.com 举报，一经查实，本站将立刻删除。

相关推荐

【啊哈！算法】算法3：最常用的排序——快速排序
【啊哈！算法】算法3：最常用的排序——快速排序       上一节的冒泡排序可以说是我们学习第一个真正的排序算法，并且解决了桶排序浪费空间的问题，但在算法的执行效率上却牺牲了很多，它的时间复杂度达到了O(N2)。假如我们的计算机每秒钟可以运行10亿次，那么对1亿个数进行排序，桶排序则只需要0.1秒，而冒泡排序则需要1千万秒，达到115天之久，是不是很吓人。那有没有既不浪费空间又可以快一点的排序算法
[数据结构与算法]模式匹配与文本处理-匿名组与命名组
匿名组 这里可能用到几个不同的分组构造。通过括号内围绕的正则表达式就可以组成第一个构造。正如稍后要介绍的一样，既然也可以命名组，大家就有考虑把这个构造作为匿名组。作为一个实例，请看看下列字符串： “08/14/57 46 02/25/59 45 06/05/85 18 03/12/88 16 09/09/90 13“ 这个字符串就是由生日和年龄组成的。如果需要匹配年两而不要生日，就可以把正则
[C#]选择排序
选择排序：从数组的起始位置处开始，把第一个元素与数组中其他元素进行比较。然后，将最小的元素方式在第0个位置上，接着再从第1个位置开始再次进行排序操作。这种操作一直到除最后一个元素外的每一个元素都作为新循环的起始点操作过后才终止。 public void SelectionSort() { int min, temp;
[数据结构与算法]模式匹配-数量词
在编写正则表达式的时候，经常会向要向正则表达式添加数量型数据，诸如”精确匹配两次”或者”匹配一次或多次”。利用数量词就可以把这些数据添加到正则表达式里面了。 数量词(+):这个数量词说明正则表达式应该匹配一个或多个紧紧接其前的字符。 string[] words = new string[] { "bad", "boy", "baad", "baaad" ,"bear", "b
[数据结构与算法]白话经典算法系列之五 归并排序的实现
来自：http://blog.csdn.net/morewindows/article/details/6678165/归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列
[C#]插入排序
插入排序算法有两层循环。外层循环会啄个遍历数组元素，而内存循环则会把外层循环所选择的元素与该元素在数组内的下一个元素进行比较。如果外层循环选择的元素小于内存循环选择的元素，那么瘦元素都想右移动以便为内存循环元素留出位置。 public void InsertionSort() { int inner, temp;
[数据结构与算法]双向链表
虽然从表内第一个节点到最后一个节点的遍历操作是非常简单的，但是反向遍历链表却不是一件容易的事情。如果为Node类添加一个字段来存储指向前一个节点的连接，那么久会使得这个反向操作过程变得容易许多。当向链表插入节点的时候，为了吧数据复制给新的字段会需要执行更多的操作，但是当腰吧节点从表移除的时候就能看到他的改进效果了。 首先需要修改Node类来为累增加一个额外的链接。为了区别两个连接，这个把指
[数据结构]树及树的遍历
八、树（Tree）树，顾名思义，长得像一棵树，不过通常我们画成一棵倒过来的树，根在上，叶在下。不说那么多了，图一看就懂：当然了，引入了树之后，就不得不引入树的一些概念，这些概念我照样尽量用图，谁会记那么多文字？树这种结构还可以表示成下面这种方式，可见树用来描述包含关系是很不错的，但这种包含关系不得出现交叉重叠区域，否则就不能用树描述了，看图：面试的时候我们经常被考到的是一种叫“二叉树”的结构，二叉
  • • 【啊哈！算法】算法3：最常用的排序——…
  • • [数据结构与算法]模式匹配与文本处理-匿…
  • • [C#]选择排序
  • • [数据结构与算法]队列的优先级
  • • [数据结构与算法]模式匹配-数量词
  • • [数据结构与算法]白话经典算法系列之五…
  • • [C#]插入排序
  • • [C#]二叉查找法
  • • [数据结构与算法]双向链表
  • • [数据结构]树及树的遍历
  • • 【啊哈！算法】算法3：最常用的排序——…
  • • [数据结构与算法]模式匹配与文本处理-匿…
  • • [C#]选择排序
  • • [数据结构与算法]队列的优先级
  • • [数据结构与算法]模式匹配-数量词
  • • [数据结构与算法]白话经典算法系列之五…
  • • [C#]插入排序
  • • [C#]二叉查找法
  • • [数据结构与算法]双向链表
  • • [数据结构]树及树的遍历
pythonJavaScriptjavaHTMLPHPreactjsC#AndroidCSSNode.jssqlrpython-3.xMysqLjQueryc++pandasFlutterangularIOSdjangolinuxswifttypescript路由器JSON路由器设置无线路由器h3c华三华三路由器设华三路由器电脑软件教程arraysdocker软件图文教程Cvue.jslaravelspring-boot

【数据结构】树状数组笔记的更多相关文章

  1. html5使用canvas实现弹幕功能示例

    这篇文章主要介绍了html5使用canvas实现弹幕功能示例的相关资料,需要的朋友可以参考下

  2. HTML5数字输入仅接受整数的实现代码

    这篇文章主要介绍了HTML5数字输入仅接受整数的实现代码,本文给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下

  3. 前端实现弹幕效果的方法总结(包含css3和canvas的实现方式)

    这篇文章主要介绍了前端实现弹幕效果的方法总结(包含css3和canvas的实现方式)的相关资料,小编觉得挺不错的，现在分享给大家，也给大家做个参考。一起跟随小编过来看看吧

  4. H5 canvas实现贪吃蛇小游戏

    本篇文章主要介绍了H5 canvas实现贪吃蛇小游戏，小编觉得挺不错的，现在分享给大家，也给大家做个参考。一起跟随小编过来看看吧

  5. ios – parse.com用于键,预期字符串的无效类型,但是得到了数组

    我尝试将我的数据保存到parse.com.我已经预先在parse.com上创建了一个名为’SomeClass’的类.它有一个名为’mySpecialColumn’的列,其数据类型为String.这是我尝试使用以下代码保存数据的代码：如果我运行这个我得到：错误：密钥mySpecialColumn的无效类型,预期字符串,但得到数组这就是我在parse.com上的核心外观：有谁知道我为什么会收到这个错误？

  6. ios – 上下文类型’NSFastEnumeration’不能与数组文字一起使用

    斯威夫特3,你会这样做吗？解决方法正如您所发现的,您不能使用as-casting将数组文字的类型指定为NSFastEnumeration.您需要找到一个符合NSFastEnumeration的正确类,在您的情况下它是NSArray.通常写这样的东西：

  7. ios – 使用大写符号在字符串swift中获取URL的正则表达式

    我尝试在文本中获取URL.所以,在此之前,我使用了这样一个表达式：但是当用户输入带有大写符号的URL时(例如Http://Google.com,它与它不匹配)我遇到了问题.我试过了：但什么都没发生.解决方法您可以使用正则表达式中的i内联标志关闭区分大小写,有关可用正则表达式功能的详细信息,请参阅FoundationFrameworkReference.(?ismwx-ismwx)Flagsetti

  8. ios – 获取资产目录文件夹中所有图像的数组

    在iOS中,是否可以获取资产目录文件夹中的图像数组？我不确定为什么会对此进行投票.我真的不知道从哪里开始.我的另一种方法是创建文件夹中所有文件的plist,但它似乎是多余的.我无法添加任何代码,因为我会添加什么？

  9. ios – 来自调试器的消息：由于内存问题而终止

    我的应用程序使用Geojson文件.我使用MapBoxSDK将MGLpolyline添加到地图中.但问题是我的文件太大,以至于应用程序崩溃并收到错误：来自调试器的消息：由于内存问题而终止.我在第一次循环时面对66234个对象.我试图将数组块化为新数组,但没有成功.请帮我解决问题.这是我在地图上绘制的代码,这里是我的testprojectongithubuseXcode8.1如果有任何不同的第三方可

  10. ios – Swift – 使用字典数组从字典访问数据时出错

    我有一个非常简单的例子,说明我想做什么基本上,我有一个字典,其值包含[String：String]字典数组.我把数据填入其中,但当我去访问数据时,我收到此错误：Cannotsubscriptavalueoftype‘[([String:String])]?’withanindexoftype‘Int’请让我知道我做错了什么.解决方法您的常量数组是可选的.订阅字典总是返回一个可选项.你必须打开它.更

随机推荐

  1. 【数据结构】单调栈

    显然，每个发射站发来的能量有可能被0或1或2个其他发射站所接受，特别是为了安全，每个发射站接收到的能量总和是我们很关心的问题。由于数据很多，现只需要你帮忙计算出接收最多能量的发射站接收的能量是多少。输入输出格式输入格式：第1行：一个整数N;第2到N+1行：第i+1行有两个整数Hi和Vi，表示第i个人发射站的高度和发射的能量值。输入输出样例输入样例：34235610输出样例：7题解中有讲解代码实现

  2. BZOJ 1798 [Ahoi2009] Seq 维护序列seq [线段树+多重标记下传]【数据结构】

    有长为N的数列，不妨设为a1,a2,…Input第一行两个整数N和P。第二行含有N个非负整数,从左到右依次为a1,aN,。表示把所有满足t≤i≤g的ai改为ai×c。操作2：“2tgc”。同一行相邻两数之间用一个空格隔开，每行开头和末尾没有多余空格。Output对每个操作3，按照它在输入中出现的顺序，依次输出一行一个整数表示询问结果。SampleInput7431234567512553242379313347SampleOutput2358HINT初始时数列为。对第5次操作，和为29+34+15+16=

  3. 陈越《数据结构》第一讲 基本概念

    陈越《数据结构》第一讲基本概念1什么是数据结构1.1引子例子：如何在书架上摆放图书？数据结构是：1.数据对象在计算机中的组织方式；2.数据对象必定与一系列加在其上的操作相关联；3.完成这些操作所用的方法就是算法。抽象数据类型数据类型-数据对象集;-数据集合相关联的操作集。抽象-与存放数据的机器无关;-与数据存储的物理结构无关;-与实现操作的算法和编程语言均无关。

  4. 陈越《数据结构》第二章 线性结构

    表中元素个数称为线性表的长度；线性表没有元素时，称为空表；表起始位置称表头，表结束位置称表尾。插入和删除操作只能在链栈的栈顶进行。

  5. 【数据结构】

    非线性结构：线性结构的元素之间具有线性关系，非线性结构中的元素之间不再是序列的关系，他们呈现的是更复杂的层次关系，即一个数据元素有且仅有一个直接前驱，但可有另个或者多个直接后继，显然比序列关系复杂常见非线性结构：树，图散列表PHP中的hashtable就是哈希表就是由数组和链表组成，一个长度为16的数组中，每个元素存储的是一个链表的头结点。

  6. 【数据结构】【C++STL】FIFO队列&amp;优先队列

    首先都需要打头文件queueFIFO队列是先进先出的就好像排队一样STL定义FIFO队列优先队列的话是有优先级存在的STL定义优先队列定义方式都是大根堆FIFO队列和优先队列都有一些操作COYG

  7. 【数据结构】 堆

    自底向上：//增加/减少已有节点值Heap_Increase_Key//向堆插入新的节点HeapInsert自顶向下：//替换堆顶后，维持堆函数KeepHeap//弹出堆顶函数Pop

  8. 【数据结构】链表

    线性表的顺序存储结构有存储密度高及能够随机存取等优点，但存在以下不足：线性表的链式存储（单链表）的实现单向循环链表的实现

  9. 伸展树(SPLAY)个人总结+模板 [平衡树]【数据结构】【模板】

    前言最近3个月内，无论是现场赛还线上赛中SPLAY出现的概率大的惊人啊啊啊！！！然而不会的我就GG了，同时发现大家都会SPLAY，，，，然后就学习了一波。——————————————————————————-附上整体代码-md贴上来太卡了,去题解里看吧维护序列的维护一堆数的

  10. BZOJ 1895 &amp; POJ 3580 supermemo [SPLAY]【数据结构】

    Ay}Ttimes.Forexample,performing“REVOLVE242”on{1,5}INSERTxP:insertPafterAx.Forexample,performing“INSERT24”on{1,5}DELETEx:deleteAx.Forexample,performing“DELETE2”on{1,5}MINxy:querytheparticipantwhatistheminimumnumberinsub-sequence{Ax…Ay}.Forexample,thecorrec

返回
顶部