Apple Tree(树状数组+dfs序)

2017年10月19日610

Apple Tree

对问题的分析设计过程

这道题需要对一颗树的节点进行如下操作:

  • 单点修改
  • 对子树节点求和

考虑到没有其他操作可以考虑使用dfs序和树状数组实现

程序中用到的数据机构和算法

该程序使用dfs序和树状数组。将树做一次dfs遍历,并记录每个节点的访问顺序,可以发现节点的子树都对应访问顺序上的一个子区间。该题可变为对序列的单点修改和区间求和,即可用树状数组解决

程序的运行情况

提交了三次才通过,提交情况如下:

在实习过程中得到的经验和体会

  1. 在提交时一定记得要把Debug信息给删除
  2. 树状数组在处理一系列简单的数列操作和询问时是一种非常简便的,可以替代线段树的视线方案

代码

%d 博主赞过: