樹狀數組學習【資料結構--樹狀數組】

樹狀數組可以在數組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