看下面这个问题(动态连续和查询):
int n; int S[maxn],A[mxan],S1[maxn]; int begin() { memset(S1,,sizeof(S1)); ;i<=n;i++) { S1[i]=S1[i-]+A[i]; S[i]=S1[i]-S1[i-lowbit(i)]; } }
void add(int i,int x) { //若需要其他操作,可以加一句: //A[i]+=x; while(i<=n) { S[i]+=x;i+=lowbit(i); } }
查询前缀和的方法与之类似,只是i+=lowbit(i);改成了i-=lowbit(i);这里不再介绍证明方法,与上面类似。代码如下:
int query2(int i) { ; ) { sum+=S[i];i-=lowbit(i); } return sum; } int query(int l,int r) { ); }
C++实用数据结构:二叉索引树的更多相关文章
-
【转载】区间信息的维护与查询(一)——二叉索引树(Fenwick树、树状数组)
在网上找到一篇非常不错的树状数组的博客,拿来转载,原文地址. 树状数组 最新看了一下区间的查询与修改的知识,最主要看到的是树状数组(BIT),以前感觉好高大上的东西,其实也不过就这么简单而已. 我们有 ...
-
二叉索引树BIT
定义 二叉索引树,binary index tree,又名树状数组,或Fenwick Tree,因为本算法由Fenwick创造. 对于数组A,定义Query(i,j) = Ai +Ai ...
-
POJ 3321 Apple Tree dfs+二叉索引树
题目:http://poj.org/problem?id=3321 动态更新某个元素,并且求和,显然是二叉索引树,但是节点的标号不连续,二叉索引树必须是连续的,所以需要转化成连续的,多叉树的形状已经建 ...
-
NYOJ 116 士兵杀敌(二)(二叉索引树)
http://acm.nyist.net/JudgeOnline/problem.php?pid=116 题意: 南将军手下有N个士兵,分别编号1到N,这些士兵的杀敌数都是已知的. 小工是南将军手下的 ...
-
HDU 1166 敌兵布阵(线段树 or 二叉索引树)
http://acm.hdu.edu.cn/showproblem.php?pid=1166 题意:第一行一个整数T,表示有T组数据. 每组数据第一行一个正整数N(N<=50000),表示敌人有 ...
-
【树状数组(二叉索引树)】轻院热身—candy、NYOJ-116士兵杀敌(二)
[概念] 转载连接:树状数组 讲的挺好. 这两题非常的相似,查询区间的累加和.更新结点.Add(x,d) 与 Query(L,R) 的操作 [题目链接:candy] 唉,也是现在才发现这题用了这个知识 ...
-
二叉索引树,LA2191,LA5902,LA4329
利用了二进制,二分的思想的一个很巧妙的数据结构,一个lowbit(x):二进制表示下的最右边的一个1开始对应的数值. 那么如果一个节点的为x左孩子,父亲节点就是 x + lowbit(x),如果是右孩 ...
-
树状数组(二叉索引树 BIT Fenwick树) *【一维基础模板】(查询区间和+修改更新)
刘汝佳:<训练指南>Page(194) #include <stdio.h> #include <string.h> #include <stdlib.h&g ...
-
1.红黑树和自平衡二叉(查找)树区别 2.红黑树与B树的区别
1.红黑树和自平衡二叉(查找)树区别 1.红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单. 2.平衡 ...
随机推荐
-
SQL Server 索引
SQL Server 中数据存储的基本单位是页(Page).数据库中的数据文件(.mdf 或 .ndf)分配的磁盘空间可以从逻辑上划分成页(从 0 到 n 连续编号).磁盘 I/O 操作在页级执行.也 ...
-
一个App完成入门篇(四)- 完成反馈页面
上一节中我们学会了如何通过点击不同按钮切换页面,这节专注于完成反馈页面的功能以及细节动画. 导入项目 添加新组件 同步新组件 完成页面布局 输入时加动画效果 弹出日期选择 直接引用UI页面 将要学习的 ...
-
基础2 JVM
1. 内存模型以及分区,需要详细到每个区放什么. //运行时数据区域 方法区 Method Area 各个线程共享的内存区域 存储已被虚拟机加载的类信息 常量 静态变量 即时编译器编译后的代码 虚拟机 ...
-
java 多线程7(线程的停止)
notify(): 是很温和的唤醒线程的方法,它不可以指定清除哪一个异常 interrupt(): 粗暴的方式,强制清除线程的等待状态,被清除的线程会接收到一个InterruptedException ...
-
mapreduce程序来实现分类
文件的内容例如以下所看到的: 5 45 8 876 6 45 要求最后的输出格式: 1 5 2 6 3 8 4 45 5 45 5 876 首先,这个题目是须要对文 ...
-
2016年团体程序设计天梯赛-决赛 L1-2. I Love GPLT(5)
这道超级简单的题目没有任何输入. 你只需要把这句很重要的话 —— “I Love GPLT”——竖着输出就可以了. 所谓“竖着输出”,是指每个字符占一行(包括空格),即每行只能有1个字符和回车. #i ...
-
小程序组件化框架 WePY 在性能调优上做出的探究
作者:龚澄 导语 性能调优是一个亘古不变的话题,无论是在传统H5上还是小程序中.因为实现机制不同,可能导致传统H5中的某些优化方式在小程序上并不适用.因此必须另开辟蹊径找出适合小程序的调估方式. 本文 ...
-
暑期OI大电影——不看后悔整个OI生涯!
惊爆~!! 2018暑期OI大电影要开始放送啦~!! 各位OI骨灰级大咖登场荧幕~!! 近四十部大电影纷至沓来~!! 著名特级导演CCF.著名特级编剧刘汝佳等纷纷给予高度评价~!! 观众朋友们,OI的 ...
-
nyoj 吃土豆
吃土豆 时间限制:1000 ms | 内存限制:65535 KB 难度:4 描述 Bean-eating is an interesting game, everyone owns an M* ...
-
cocos2dx2.x 创建项目
cocos2d-x下载地址:http://www.cocos2d-x.org/download 2.0之后的创建项目比较easy了 第一步,首先 cd cocos2d-x-2.2.1/tools/pr ...