浅谈树状数组
2018-06-17 21:45:54来源:未知 阅读 ()
最近学了树状数组,给我的感觉就是 这个数据结构好神奇啊^_^
首先他的常数比线段树小,其次他的实现复杂度也远低于线段树 (并没有黑线段树的意思=-=)
所以熟练掌握他是非常有必要的。。
关于树状数组的基础知识与原理网上一搜一大堆,我就不赘述了,就谈一些树状数组的应用好了
(推荐一篇写得比较好的博客:https://www.cnblogs.com/ECJTUACM-873284962/p/6380245.html)
1,单点修改,求区间和
#define lowbit(x) (x&-x) // 设 x 的末尾零的个数为 y , 则 lowbit(x) == 2^y 。 -x表示的是x在二进制中的补码
void Update(int i,int v) // 初始化与单点修改 { while(i <= n) { c[i] += v ; i += lowbit(i) ; } } inline int Sum(int i) // 区间求和 { int res = 0 ; while(i > 0) { res += c[i] ; i -= lowbit(i) ; } return res ; }
2,区间修改,单点查询
这里要用到差分的思想
创建一个差分数组c[],令c[i] = a[i] - a[i-1] (a[i] 表示原本的第i个数)
则a[i] = ( a[i] - a[i-1] ) + ( a[i-1] - a[i-2] ) + ...... + ( a[2] - a[1] ) +a[1]
= c[i] + c[i-1] + ...... + c[2] + c[1]
所以单点查询变成了区间求和
那么区间修改怎么办呢 ?
我们看这样一个例子:
a 1 3 4 5 7 10
c 1 2 1 1 2 3
若我们令区间[2,4]加2,则
a 1 5 6 7 9 10
c 1 4 1 1 2 1
我们可以发现只有c[2]和c[5]的数值改变了,其实原理也很好想,区间内的前后元素差是不变的,只有(区间第一个元素与前一个元素的差) 和 (区间后第一个元素与区间末尾元素的差) 改变了。所以区间修改问题变成了单点修改问题。
for(int i=1;i<=n;i++) { a[i] = read() ; Update(i,a[i]-a[i-1]); } /* int x=0,y=0; // 注释掉的内容是空间上的优化(初学者建议先跳过) for(int i=1;i<=n;i++) { if(i%2) { x = read() ; Update(i,x-y); } else { y = read() ; Update(i,y-x) ; } } */ int ii ; int k,x,y; for(int i=1;i<=m;i++) { ii = read() ; if(ii == 1) { x = read() ; y = read() ; k = read() ; Update(x,k); Update(y+1,-k); } if(ii == 2) { x = read() ; printf("%d\n",Sum(x)); } }
(洛谷有对应的模板题 P3374 与 P3368)
上述就是树状数组最基础的两个应用,日后更深入的学习后再来更新。
——end ;
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 纯虚函数与基类指针数组的运用 代码参考 2020-04-30
- STL之deque 2020-04-29
- C++基础 学习笔记六:复合类型之数组 2020-04-25
- 寻找两个有序数组的中位数 2020-04-09
- STL之vector 2020-04-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash