学步园

//最基本的树状数组
#include<iostream> 
#include<cstring>
#define size 1000
using namespace std;
int A[size],C[size],N;

void add(int x,int d);
int lowbit(int x);
int sum(int x);
void build();

int lowbit(int x)   //求x得二进制表达式中最右边的1对应的值（不是序号）
{
    return x&-x;
}
void build()  //初始化数组
{
    for(int i=1;i<=N;i++)
    {
        add(i,A[i]);
    }
}
void add(int x,int d)  //在X的位置加上大小为d的数
{
    while(x<=N)
    {
        C[x]+=d;
        x+=lowbit(x);
    }
}
int sum(int x)  //求1到X的和
{
    int ret=0;
    while(x>=1)
    {
        ret+=C[x];
        x=x-lowbit(x);
    }
    return ret;
}
int main()
{
    cin>>N;
    memset(C,0,sizeof(C));
    for(int i=1;i<=N;i++)
    {
        cin>>A[i];
    }
    build();
    for(int i=1;i<=N;i++)
    {
        cout<<C[i]<<" ";
    }
    cout<<endl;
    for(int i=1;i<=N;i++)
    {
        cout<<sum(i)<<" ";
    }
    cout<<endl;
    return 0;

}