一、使用原因
一般的数组修改操作的复杂度是O(1),求前缀和操作的复杂度是O(n);而同时维护一个前缀和数组时修改操作的复杂度是O(n),求前缀和操作复杂度是O(1);
当我们有m次操作时,时间复杂度就会达到O(mn),达到了平方级别,而我们维护一个树状数组时求前缀和和修改操作的复杂度是O(logn),总时间复杂度只有O(mlogn),达到了很快的程度。
首先要了解lowbit运算,二进制分解下最小的2的次幂。即当我们求11100的lowbit时返回的是100(二进制下)。
1 int lowbit(int x) 2 { 3 return x & -x; 4 }
二、基本思想
树状数组的本质思想是使用树结构维护”前缀和”,从而把时间复杂度降为O(logn)。
考虑一个区间[1,x],对于x,我们将其二进制展开成x=2 ^ i1 + 2 ^ i2 + 2 ^ i3 .......+ 2 ^ ik,设i1 > i2 > i3 >.....> ik,所以我们可以把这个区间分成 log x 个小区间,长度分别为([1,2 ^ i1]),