普通线段树
问题 给定长为 n n 的序列 A ，有 m m 次操作： ins x p ：给 A[x] 增加 p 。 ask l r ：询问 A [ l , r ] A [ l , r ] 的区间和。 n , m ≤ 500000 n , m ≤ 500000 . 分治 暴力显然是 O ( n m ) O ( n m ) 的。我们来考虑分治。 假设我们查询 [ 1 , 1029 ] [ 1 , 1029 ] 的区间和。如果我们手上已经有 [ 1 , 1024 ] [ 1 , 1024 ] 的区间和，那么我们就把问题剖成了两段： S ( 1 , 1029 ) = S ( 1 , 1024 ) + S ( 1025 , 1029 ) S ( 1 , 1029 ) = S ( 1 , 1024 ) + S ( 1025 , 1029 ) . 这是可以很快得出结果的。 按照上面的思路，假设序列长度为 2048 2048 ，那么我们就把整个序列剖成 [ 1 , 1024 ] , [ 1025 , 2048 ] [ 1 , 1024 ] , [ 1025 , 2048 ] ，然后进一步剖成 [ 1 , 512 ] , [ 513 , 1024 ] , [ 1025 , 1536 ] , [ 1537 , 2048 ] [ 1 , 512 ] , [ 513 , 1024 ] , [ 1025 , 1536 ] , [ 1537 , 2048 ] ，这样剖下去，我们就把整个序列剖成了共 2 n 2 n 个区间。 这就是线段树。 普通线段树 线段树是拥有分治结构的树。它长成这样（借个图）： 除了叶子节点，每个节点都有两个儿子。 [ l , r ] [ l , r ] 的左儿子是 [ l , m i d ] [ l , m i d ] ，右儿子是 [ m i d + 1 , r ] [ m i d + 1 , r ] . 那么题目中的操作就可以这样来处理： 添加操作：对于 x ，找到所有包含它的区间（共 log n log n 个），给这些区间的和加上 p 。 查询操作则要困难一些。我们用一个递归过程实现它： #define LE(x) ((x)*2) //用数组保存完全二叉树，x*2为...