2019WIT Summer Camp

发布于 8 天前  11 次阅读


WIT Summer Camp —— Lzh 之假前培训 —— 分块、线段树、树状数组(区间更新,区间查询)板子题

单点更新,区间查询(模板)

分块

在上一讲的基础上,增加了一个add数组用于辅助更新。

sum数组:用于记录初始的每一块内的和以及非整块更新时的增加量

add数组:初始为0,用于记录整块更新时的增加量

所以在查询区间和的时候,需要上述两个数组在相应区间的和。

查询非整块的和:暴力扫一遍,计算每一个num以及add在这段长度上的增量

查询整块的和:该块的sum以及add在这块的长度上的增量

 

 


Σσ(・Д・;)我我我什么都没做!!!