首页 > 代码库 > 树状数组
树状数组
背景：
需要维护前缀和 S[i]=A[1]+A[2]+...+A[i]。 但修改了任意一个 A[i] 后, S[i]，...，S[n] 会发生变化，调整需要 O(n) 时间。
因此， 引入 “树状数组”，它的修改与求和都是 O(logn) 的，效率很高。
树状数组：即一个数组 C[]，如下图.
核心函数：
int A[N] = {0,1, 2, 3, 4, 5, 6, 7, 8, 9};int C[N] = {0};int Lowbit(int x) { return x & (-x);}int Sum(int end) { int sum = 0; while(end > 0) { sum += C[end]; end -= Lowbit(end); } return sum;}/* update node i and its fathers */void update(int i, int val) { while(i < N) { C[i] += val; i += Lowbit(i); // get its father }}void init() { for (int i = 1; i < N; ++i) update(i, A[i]);}C[i]表示 A[i-2k+1]到 A[i]的和（共 2k 个数），而 k 则是 i 在二进制时末尾 0 的个数，或者说是 i 用 2 的幂方和表示时的最小指数。
树状数组
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。