线段树

线段树的原理：把[1…n]分解为若干子区间（数量上不超过4*n），将每个子区间[L,R]都分解。这里必须要符合区间加法。
符合区间加法的例子：
数字之和——总数字之和 = 左区间数字之和 + 右区间数字之和
最大公因数(GCD)——总GCD = gcd( 左区间GCD , 右区间GCD );
最大值——总最大值=max(左区间最大值，右区间最大值)