Open wzr1005 opened 5 years ago
https://wzr1005.github.io/2019/03/19/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84-Binary-Indexed-Tree/
树状数组，解决动态前缀和问题的数据结构 如数组元素 a1, a2, a3, … an 询问a1 + a2 + a3 …+ am 修改ai (1 <=i<=n) 暴力复杂度 O(n^2) d[6] = a5 + a6 6的二进制是 110 末尾有一个0 则d[6]包含2^1个元素。 d[8] = a1 + a2 … + a8, 8二进制是1000 2^3
https://wzr1005.github.io/2019/03/19/%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84-Binary-Indexed-Tree/
树状数组，解决动态前缀和问题的数据结构 如数组元素 a1, a2, a3, … an 询问a1 + a2 + a3 …+ am 修改ai (1 <=i<=n) 暴力复杂度 O(n^2) d[6] = a5 + a6 6的二进制是 110 末尾有一个0 则d[6]包含2^1个元素。 d[8] = a1 + a2 … + a8, 8二进制是1000 2^3