- #include <iostream>
- using namespace std;
- const int maxn=10000;
- int a[maxn];
- int c[maxn];
- void make_c(int i){
- int x=i&(-i); //2^xi=i&(-i); 求区间范围大小, x=2^xi
- for(int left=i-x+1;left<=i;left++) // 区间范围 [i-2^x+1,i]
- {
- c[i]=c[i]+a[left]; //c[i] 表示该区间范围内的元素之和
- }
- }
- void updata(int i,int num,int n){ // 将 a[i] 更改为 new, 更新 c[i] 数组
- while(i<=n)
- {
- c[i]=c[i]+num;
- i=i-i&(-i);
- }
- }
- int sum(int i){ // 前 i 个元素求和
- int s=0;
- while(i>0)
- {
- s+=c[i];
- i-=i&(-i);
- }
- return s;
- }
- int main(){
- int n;
- cin>>n;
- for(int i=1;i<=n;i++)
- {
- cin>>a[i];
- }
- for(int i=1;i<=n;i++)
- {
- make_c(i);
- }
- int ans=sum(4);
- cout<<ans<<endl;
- for(int i=1;i<=n;i++)
- cout<<c[i]<<" ";
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3259170.html