背景
在《秋天的第一杯奶茶》一题中,全机房都rush了一个莫队,莫队左右端点的指针移动操作是一个区间查询/区间修改的问题。zzh毫不犹豫的拍了个线段树板子,然后:

凭借着线段树的大常数成功垫底。
推导
转自OI-wiki
若维护序列 a 的差分数组 b ,此时我们对 a 的一个前缀 r 求和,即 ∑i=1rai ,由差分数组定义得 ai=∑j=1ibj
进行推导
===i=1∑raii=1∑rj=1∑ibji=1∑rbi×(r−i+1)i=1∑rbi×(r+1)−i=1∑rbi×i
区间和可以用两个前缀和相减得到,因此只需要用两个树状数组分别维护 ∑bi 和 ∑i×bi ,就能实现区间求和。
效果