树状数组学习【数据结构--树状数组】

树状数组可以在数组A[1...n]上，在O(logn)的时间内完成以下任务

1. 给A[i] 加上一个数
2. 求A[1]+...+A[i]的和

实现原理参考下图，很神奇就是了。

The Code

#include<bits/stdc++.h>

const int maxn=1e5+5;

int Tree[maxn];
inline int lowbit(int x)
{
    return (x&-x);
}

void add(int x,int value)
{
    std::cout<<value<<" : ";
    for(int i=x;i<=maxn;i+=lowbit(i))
    {
        Tree[i]+=value;
        std::cout<<i<<" ";
        
    }
    std::cout<<std::endl;
}

int get(int x)
{
    int sum=0;
    for(int i=x;i;i-=lowbit(i))
        sum+=Tree[i];
    return sum;
}

int main()
{
    int arr[]={0,1,7,3,0,7,8,3,2,6,2,1,1,4,5};
    std::cout<<666<<std::endl;
    // 从1开始
    for(int i=1;i<15;i++)
    {
        add(i,arr[i]);      
    }
    for(int i=1;i<15;i++)
    {
        std::cout<<i<<" : "<<lowbit(i)<<" : "<<get(i)<<std::endl;
    }
    
    return 0;
}
           

转载于:https://www.cnblogs.com/shengwang/p/9809044.html