对线段树的理解

线段树的介绍：http://fqq11679.blog.hexun.com/21722866_d.html#commentsList

C[i]表示A[i-2^k+1]到A[i]的和，而k则是i在二进制时末尾0的个数，即去掉二进制i末尾的零的数到i的这个区间的数之和，在更新时必须快捷的更新所有包含数i的区间，在线段树中体现为必须更新C[i]的父节点及其以上的结点，在求前缀和时必须快捷的找到左边紧邻C[i]区间的那个最大的区间。

2^k=i&(i^(i-1))=i&(-i)，C[i]的区间长度为i-(i-2^k+1)+1=2^k,因而紧邻C[i]的那个最大的区间为C[i-2^k],而在求其父节点x时，由于C[x]和C[i]有相同的区间下届，即两者所拥有的区间的起点相同，且父节点的层数比子节点大1，因而有i-2^k+1=x-2^(k+1)+1,即父节点x=i+2^k。