首页 > 编程语言 > 详细

树状数组差分求前缀和的前缀和

时间:2019-08-20 01:47:18      阅读:192      评论:0      收藏:0      [点我收藏+]

既然我们知道树状数组可以差分求前缀和 

那么就可以对其进行 前缀和 求变量值

展开可得 

$(k+1)*\sum_{i}^n c[i]-\sum_{i}^n i*c[i]$

两个 树状数组可以搞定

 

顺便提一下DFS序  可以将树上问题转化为区间问题 对节点重新编号 并且有从属关系  从而 利用各种数据结构 例如 树剖  树状数组解决

树状数组差分求前缀和的前缀和

原文:https://www.cnblogs.com/OIEREDSION/p/11380443.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!