...
| 代码块 |
|---|
int getsum(int x) {
int ans = 0;
while(x >= 1) {
ans += c[x];
x -= lowbit(x);
}
return ans;
} |
同样代入上面的表格进行验证即可。
最后是如何建立树状数组，示例代码如下，这时在每确定一个最后是如何建立树状数组，示例代码如下，这里在每确定一个c[i]时，都会更新一次c[i]的直接父结点，则于父结点的值只来自于子结点求和，所以建树的时间复杂度为O的直接父结点，由于父结点的值只来自于子结点求和，所以建树的时间复杂度为O(n)：
| 代码块 |
|---|
#define MAXN 1005
int a[MAXN];
int c[MAXN];
int n;
void init() {
for(int i = 1; i <= n; i++) {
c[i] += a[i];
int j = i + lowbit(i);
if(j <= n) t[j] += t[i];
}
} |
...