线段树浅层学习

AcWing 246. 区间最大公约数

• 题意简述：区间加，区间 gcd.

• 解：
  根据更相减损术，有 (gcd(x,y)=gcd(x,y-x)).
  一般地，有 (mathbf{gcd(a_1,a_2,cdots,a_n)=gcd(a_1,a_2-a_1,cdots,a_n-a_{n-1})}).
  这个结论是关于 gcd 的一个重要结论（另一个重要结论是 (gcd(f_n,f_m)=f_{gcd(n,m)})，其中 (f) 为斐波那契数列）。
  有了这个结论，我们就可以使用线段树维护关于 (a) 数组的差分数组 (b_i=a_i-a_{i-1}(a_0=0)) 的和与 gcd.
  单点修改，区间查询。时间复杂度 (O(mlog n)).