概念 假设有编号从1到n的n个点,每个点都存了一些信息,用[L,R]表示下标从L到R的这些点。线段树的用处就是,对编号连续的一些点进行修改或者统计操作,修改和统计的复杂度都是O(log(n)).线段树的原理,就是,将[1,n]分解成若干特定的子区间(数量不超过4*n),然后,将每个区间[L,R]都分解为少量特定的子区间,通过对这些少量子区间的修改或者统计,来实现快速对[L,R]的修改或者统计。 要点 用线段树统计的东西,必须符合区间加法,否则,不可能通过分成的子区间来得到[L,R]的统计结果。符合区间加法的例子:数字之和——总数字之和 = 左区间数字之和 + 右区间数字之和最大公因数(GCD)...