哪个网站做签约设计师比较好,做企业网站开发哪家好,长春建站程序,网站编辑制作问题的提出#xff1a;是否可以用线性数据结构的方法解决动态统计子树权和的问题呢#xff1f; 有的#xff0c;树状数组。 假设当前数组为a[]#xff0c;元素个数为n。 1. 子区间的权和数组为sum#xff0c;那么数组a[]中 i 到 j这段区间的数组元素和为sum[i,j] a[k]的累…问题的提出是否可以用线性数据结构的方法解决动态统计子树权和的问题呢 有的树状数组。 假设当前数组为a[]元素个数为n。 1. 子区间的权和数组为sum那么数组a[]中 i 到 j这段区间的数组元素和为sum[i,j] a[k]的累加 【k属于(i-j)】 2. 现在定义前缀和数组s[]s[i]代表从a[i]---a[i]的和那么又可以这样表示 sum[i,j] s[j]-s[i-1]. 3. lowbit(k)为整数k的二进制表示中 右边第一个1所代表的数字lowbit(k)k(-k). 4. 树状数组为c[]c[k]存储的是从a[k]开始向 低的下标那边数lowbit(k)个元素之和一层遍历。 注意我们要把a[]数组的元素从下标1开始存储. 这里列举一下 c[1]a[1]; s[1]c[1]; c[2]a[2]a[1]; s[2]c[2]; c[3]a[3]; s[3]c[3]c[2]; c[4]a[4]a[3]a[2]a[1]; s[4]c[4]; c[5]a[5]; s[5]c[5]c[4]; c[6]a[6]a[5]; s[6]c[6]c[4]; c[7]a[7]; s[7]c[7]c[6]c[4]; c[8]a[8]a[7]a[6]a[5]a[4]a[3]a[2]a[1]; s[8]c[8]; c[9]a[9]; s[9]c[9]c[8]; 5. 计算每个s[i]的复杂度是O( log2(n) ). 6. 代码 #include stdio.h
#include string.hint a[101];
int c[101];
int s[101];int lowbit(int x)
{return x(-x);
}int sum(int x)
{int s0;while(x0){sc[x];xx-lowbit(x);}return s;
}int main()
{int i, j, k;for(i1; i10; i)a[i]i;//创建a[]数组for(i1; i10; i){//计算每个c[i]c[i]0;//c[i]从初始为0for(ji-lowbit(i)1; ji; j){c[i]a[j];}}for(i1; i10; i){s[i]sum(i);//计算i的前缀数组和}return 0;
}转载于:https://www.cnblogs.com/yspworld/p/4724552.html
