假設我們就只會O(log N)的單點修改、區間求和，能做這題嗎？答案是可以

令S(x)代表某個時刻陣列a[0]+...+a[x]的值

然後我們做了一次操作是「把a[l], ..., a[r]的值都加上u」

做完之後令此時陣列a[0]+...+a[x]的值為S'(x)

那麼S'如何用S表示？我們會發現：

S'(x)=

S(x) if x<l

S(x)+u(x-l+1) if l<=x<=r (或l<=x<r)

S(x)+u(r-l+1) if r<x (或r<=x)

我們發現多出來的項都是一次式，而且範圍[l, r]內的一次項與常數項變化、以及範圍(r, .]的常數項變化都是一樣的

於是容易想到：我們存兩個陣列 A 與 B，分別代表一次項與常數項，並且保持：

S(x)= (A[0]+...+A[x])x+(B[0]+...+B[x])

(初始化的方式為A全零而B就是一開始的陣列)

那麼計算S(x)就是分別對陣列A、B做區間求和後代值、並且「把a[l], ..., a[r]的值都加上u」這個操作只需要修改A和B至多兩個位置的值

這麼一來就完成了！

這個方法的進階應用可以練習CSES的這題： https://cses.fi/problemset/task/1736

這題就不能用簡單的lazy tag囉