算法合集之树状数组.doc

简单地研究了一下这个数据结构在这做个总结摘要 树状数组是一个查询和修改复杂度都为log(n)的数据结构假设数组a[1.n]那么查询a[1] + + a[i] 的时间是log级别的而且是一个在线的数据结构支持随时修改某个元素的值复杂度也为log级别 来观察一下这个图 ? ? 令这棵树的结点编号为C1C2Cn令每个结点的值为这棵树的值的总和那么容易发现 C1 = A1 C2 = A1 + A2 C3