初步感受
已知 \(a_i\),求 \(\sum_{i=1}^7 a_i\)。
暴力:
\(ans=a_1+a_2+a_3+a_4+a_5+a_6+a_7\)
时间复杂度:\(O(n)\)
树状数组:
已知 \(A=\sum_{i=1}^4 a_i\),\(B=\sum_{i=5}^6 a_i\),\(C=\sum_{i=7}^7 a_i\),则 \(ans=A+B+C\)
时间复杂度:\(O(\log n)\)
这就是树状数组能快速求解信息的原因:我们总能将一段前缀 \([1,n]\) 拆成 不多于 \(\log n\) 段区间,使得这 \(\log n\) 段区间的信息是 已知的。
于是,我们只需合并这 \(\log n\) 段区间的信息,就可以得到答案。相比于原来直接合并 \(n\) 个信息,效率有了很大的提高。
树状数组具体长这样:
标签:log,树状,sum,数组,ans,复杂度 From: https://www.cnblogs.com/reclusive2007/p/17617246.html