高级数据结构--树状数组

2021-01-28 07:16

阅读：810

标签：space owb 数组位置 size eid 区间修改 upd http

　　　　本地搬运~

　　　 关于树状数组的学习，强烈推荐这个视频：https://www.bilibili.com/video/av26371798?from=search&seid=2141442207537065040

　　　　1：树状数组：查询和修改复杂度都为log(n)的数据结构，本身可用于单点修改区间查询，加入辅助数组后可实现区间修改：POJ3468

　　　 2：参考视频，我整理了这张图：

　　　　单点更新：

cin>>x;
update(i,x);
void update(int id,int x)
{
    for(int i=id;ilowbit(i))
        c[i]+=x;
}

　　　　 查询[L,R]的区间和

cin>>i>>j;
cout1)endl;
int getsum(int id)
{
    int sum=0;
    for(int i=id;i>=1;i-=lowbit(i))
        sum+=c[i];
    return sum;
}

　　　　lowbit求的是C[i]的i变为二进制后，从右往左找到第一个1的出现位置，固定这个1，其他全为0，再化为十进制。

int lowbit(int i)
{
    return i&(-i);
}

　　　　HDU1166:基本板子题：

技术图片

#include
#include
#includeusing namespace std;
const int maxn=5e4+10;
int c[maxn],n;
int lowbit(int i)
{
    return i&(-i);
}
void update(int id,int x)
{
    for(int i=id;ilowbit(i))
        c[i]+=x;
}
int getsum(int id)
{
    int sum=0;
    for(int i=id;i>=1;i-=lowbit(i))
        sum+=c[i];
    return sum;
}
int main()
{
    int t;
    cin>>t;
    int ac=1;
    while(t--)
    {
        printf("Case %d:\n",ac++);
        cin>>n;
        int x;
        memset(c,0,sizeof(c));
        for(int i=1;i)
        {
            cin>>x;
            update(i,x);
        }
        string ch;
        while(cin>>ch)
        {
                if(ch=="End")
                {
                    break;
                }
                if(ch=="Add")
                {
                    int i,j;
                    cin>>i>>j;
                    update(i,j);
                }
                if(ch=="Sub")
                {
                    int i,j;
                    cin>>i>>j;
                    update(i,-j);            
                }
                if(ch=="Query")
                {
                    int i,j;
                    cin>>i>>j;
                    cout1)endl;
                }
        }
    }
}

高级数据结构--树状数组

标签：space owb 数组位置 size eid 区间修改 upd http

原文地址：https://www.cnblogs.com/liyexin/p/12838842.html

上一篇：Java中的动态定义数组

下一篇：【剑指offer】【位运算】56 - I. 数组中数字出现的次数

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：高级数据结构--树状数组
文章链接：http://soscw.com/index.php/essay/48125.html

亲，登录后才可以留言！

高级数据结构--树状数组

评论

热门文章

推荐文章

最新文章

置顶文章