数据结构-树状数组

作者：小丑西瓜9 | 2024-04-16 15:00:44

踩

数据结构-树状数组

树状数组是一种类似于前缀和的数据结构，但是前缀和的修改操作是 O(n)的，查询是 O(1) 的。所以就有了树状数组这个数据结构，它的两种操作被中和了，都是 O(logn) 的。

int nums[N];
//算出最后一位1的位置
int lowbit (int x) 
{    
    return x & -x;
}
//查询前缀和，时间复杂度O(logn)
int ask(int x)
{
    int res=0;
    for(;x;x-=lowbit(x)) res+=nums[x];
    return res;
}
//单点修改，时间复杂度O(logn)
int add(int x,int y)//nums[x]+y
{
    for(;x<=n;x+=lowbit(x)) nums[x]+=y;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/434859