数据结构（2）树状数组

news/2024/7/8 1:13:37

活动 - AcWing

参考：《算法竞赛进阶指南》-lyd

目录

一、概念

1.主要功能

2.实现方式

3.

二、例题

1.树状数组和逆序对

2.树状数组和差分

3. 两层差分

4. 结合二分

 

一、概念

1.主要功能

树状数组可以完成的功能主要有：

  • 维护序列的前缀和
  • 单点修改

上述两个操作在树状数组中都是logn级别的。对比前缀和数组和原始序列

前缀和数组查询前缀和o（1），但是单点修改o（n）。原始数组求前缀和o（n），单点修改o（1）。所以在大量的查询和修改操作并存的情况下，树状数组表现更优秀。

2.实现方式

注意下标从1开始

对一个较大的连续线性范围进行统计时，我们把它按照2的整数次幂分成若干个小范围进行预处理和计算。若一个正整数x的二进制表示为a_{k-1}a_{k-2}...a_2a_{1}a_{0}，设其中等于1的位分别是\left \{ a_{i_1},a_{i_2},a_{i_3},...,a_{i_m} \right \}则正整数x可以被“二进制分解成”：

x=2^{i_1}+2^{i_2}+...+2^{i_m}

设i1>i2>...>im，则区间[1,x]可被划分为logx个小区间：

  1. 长度为2^i1的区间[1,2^i1]
  2. [2^i1 + 1,2^i1 + 2^i2]
  3. [2^i1 + 2^i2 + 1,2^i1 + 2^i2 + 2^i3]
  4. ......
  5. [2^i1 + 2^i2 + 2^i3+...+ 2^im-1 + 1,2^i1 + 2^i2 + 2^i3+...+ 2^im]

他们的特点是：若区间结尾为R，则区间长度等于lowbit（R）

树状数组就是基于上述思想的数据结构。对于原始序列a，我们建立树状数组tr，存储划分后每个区间的和。即：

tr[x]=\sum_{i=x-lobit(x+1)}^{x} a[i]

那么求前缀和可转化为

for(int i=x;i<=n;i+=lowbit(i)) res+=tr[x]
return res

有logn个区间，所以复杂度logn。

接下来考虑怎么构建这样的树状数组：

画一下经典1-16的区间图。很容易发现之中的树状关系。接下来我们找一下子节点和父节点的下标的关系。

对于一个子节点，父节点编号y和子节点编号x有关系：y=x+lowbit(x)

对父节点，子节点编号为

for(;x;x-=lowbit(x))

3.

对于查询操作：遍历所有子节点u1=x，u2=u1-lowbit(u1),.....un=1

对于修改操作，设单点x增加d

则把所有相关的父节点更新。父节点编号u1=x,u2=u1+lowbit(u1)......un=N

二、例题

1.树状数组和逆序对

 dp思想：将所有V和A按中间顶点位置划分。

对于顶点i，其V数量为在它左边比他大的数的个数  乘以  在它右边比他大的数的个数

A数量反之。

因此我们需要处理：在遍历到第i个点前，比y（i）大的数的个数和比y（i）小的数的个数

对此，我们应该记录，在遍历到i点前，每个y（x）出现的次数

这样，比yi大的数的个数为sum（n）-sum（y），比yi小的数的个数为sum（y）

处理完之后add（yi，1）即可

因此需要维护一个查询前缀和，支持单点修改的数组，并且复杂度不能n方，树状数组符合要求。

V A 数量 正反遍历一遍即可

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int N =2e5+10;

typedef long long LL;

int n;
int a[N];
int tr[N];//树状数组的原数组是 数字i出现的次数。
int Greater[N];
int Lower[N];


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

void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

int sum(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i))
    {
        res+=tr[i];
    }
    return res;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++)
    {
        int y=a[i];
        Lower[i]=sum(y-1);
        Greater[i]=sum(n)-sum(y);
        add(y,1);
    }
    memset(tr,0,sizeof tr);
    LL resV=0,resA=0;
    for(int i=n;i;i--)
    {
        int y=a[i];
        resV+=(LL)Greater[i]*(sum(n)-sum(y));
        resA+=(LL)Lower[i]*(sum(y-1));
        add(y,1);
    }
    cout<<resV<<" "<<resA<<endl;
    return 0;
}


作者：yankai
链接：https://www.acwing.com/activity/content/code/content/5174438/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.树状数组和差分

 题目要求：区间增加，单点查询。

用树状数组维护原数组的差分数组，即可把条件转化为单点增加，区间查询。符合要求

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

typedef long long LL;
const int N =1e5+10;

int n,m;
int a[N];
int tr[N];

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

void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

LL sum(int x)
{
    LL res=0;
    for(;x;x-=lowbit(x)) res+=tr[x];
    return res;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        add(i,a[i]-a[i-1]);
    }
    while(m--)
    {
        char op[2];
        int l,r,d;
        scanf("%s%d",op,&l);
        if(*op=='C')
        {
            scanf("%d%d",&r,&d);
            add(l,d),add(r+1,-d);
        }
        else
        {
            cout<<sum(l)<<endl;
        }
    }
    return 0;
}

作者：yankai
链接：https://www.acwing.com/activity/content/code/content/5174626/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

3. 两层差分

 题目要求：区间增加，区间查询。

 推导一下：可知a1=b1，a2=b1+b2。。。。写成三角矩阵，补齐右上角

可推导出：


\sum_{i=1}^{x}\sum_{j=1}^{i} b[j]=(1+x)*\sum_{i=1}^{x}b[i]-\sum_{i=1}^x ib[i]
 

因此维护一个a的差分数组b，再维护一个i*ai的差分数组即可。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#include<cstdio>

typedef long long LL;
const int N =1e5+10;


int n,m;
LL tr1[N];
LL tr2[N];
int a[N];

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

void add(LL tr[],int x,LL c)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

LL sum(LL tr[],int x)
{
    LL res=0;
    for(;x;x-=lowbit(x)) res+=tr[x];
    return res;
}

LL presum(int x)
{
    return (x+1)*sum(tr1,x)-sum(tr2,x);
}


int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        int b=a[i]-a[i-1];
        add(tr1,i,b);
        add(tr2,i,(LL)b*i);
    }

    while(m--)
    {
        char op[2];
        int l,r,d;
        scanf("%s%d%d",op,&l,&r);
        if(*op=='C')
        {
            scanf("%d",&d);
            add(tr1,l,d),add(tr1,r+1,-d);
            add(tr2,l,l*d),add(tr2,r+1,-(r+1)*d);
        }
        else
        {
            cout<<presum(r)-presum(l-1)<<endl;
        }
    }
    return 0;
}

作者：yankai
链接：https://www.acwing.com/activity/content/code/content/5174858/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

4. 结合二分

只知道前面有几头比第i头低。

因此我们从后往前推导，由于身高各不相同，设：备选序列1~n，

我们直接可以知道第n头就是第ai+1高的，即ai+1，则往前推，第n-1头就是备选序列去掉ai+1之后，剩下第a（n-1）+1高的。

因此我们需要的操作是：快速找出序列中第k高的，转换一下，备选序列可选即1，已被选为0，则操作变为快速找出一个x，使得sum（x）==k。因此树状数组可做，找出这个x可用二分查找

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;

const int N=1e5+10;
int n;
int a[N];
int tr[N];

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

void add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
int sum(int x)
{
    int res=0;
    for(;x;x-=lowbit(x)) res+=tr[x];
    return res;
}


bool check(int mid,int k)
{
    return sum(mid)>=k;
}


int main()
{
    cin>>n;
    for(int i=2;i<=n;i++)
    {
        cin>>a[i];
    }

    for(int i=1;i<=n;i++)
        add(i,1);


    for(int i=n;i>=1;i--)
    {
        int k=a[i];
        k++;
        int l=1,r=n;
        while(l<r)
        {
            int mid=l+r>>1;
            if(check(mid,k))  r=mid;
            else l=mid+1;
        }
        a[i]=l;
        add(l,-1);
    }
    for(int i=1;i<=n;i++) cout<<a[i]<<endl;
    return 0;

}

作者：yankai
链接：https://www.acwing.com/activity/content/code/content/5175077/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

http://lihuaxi.xjx100.cn/news/633559.html

相关文章

唤醒手腕 Go 语言开发学习笔记（基本简介、环境安装、基础知识）

唤醒手腕 Go 语言开发学习笔记（基本简介、环境安装、基础知识）

1. Go语言简介 Go&#xff08;又称 Golang&#xff09;是 Google 的 Robert Griesemer&#xff0c;Rob Pike 及 Ken Thompson 开发的一种静态强类型、编译型语言。Go 语言语法与 C 相近&#xff0c;但功能上有&#xff1a;内存安全&#xff0c;GC&#xff08;垃圾回收&#xf…
阅读更多...
研究发现，大多数长期 COVID 影响在感染后一年内消退

研究发现，大多数长期 COVID 影响在感染后一年内消退

英国医学杂志今天发表的一项来自以色列的大型研究发现&#xff0c;轻度 COVID-19 感染后出现的大多数症状或病症会持续数月&#xff0c;但在一年内恢复正常。 特别是接种过疫苗的人&#xff0c;呼吸困难的风险较低。这通常也是轻度感染后最常见的影响。相比之下&#xff0c;比未…
阅读更多...
Java线程的六种状态

Java线程的六种状态

前言&#xff1a;其实线程的状态在操作系统的PCB中就对其进行了描述&#xff0c;但是Java中觉得自带的状态并不是特别好&#xff0c;于是引入了线程在Java中的六种状态。 (1) NEW 安排了工作还未行动&#xff0c;即&#xff1a;Thread对象创建出来了&#xff0c;但是内核的PCB…
阅读更多...
一文读懂Go Http Server原理

一文读懂Go Http Server原理

hello大家好呀，我是小楼，这是系列文《Go底层原理剖析》的第二篇，依旧是分析 Http 模块，话不多说，开始。从一个 Demo 入手 俗话说万事开头难，但用 Go 实现一个 Http Server 真不难，简单到什么程度？起一个 Server，并且能响应请求，算上包名、导入的依赖，甚至空行，也就…
阅读更多...
Java多线程：线程的优先级 || 线程的中断 || 线程的分类 || 线程的定时器

Java多线程：线程的优先级 || 线程的中断 || 线程的分类 || 线程的定时器

Java多线程&#xff1a;线程的优先级 || 线程的中断 || 线程的分类 || 线程的定时器 每博一文案 正如村上春树所说&#xff1a;“当暴风雨过去&#xff0c;你不会记得自己是如何度过的&#xff0c;你甚至不确定&#xff0c;暴风雨是否真正结束了&#xff0c; 但你已不再是当初…
阅读更多...
Java异常情况了解

Java异常情况了解

作者&#xff1a;爱塔居的博客_CSDN博客-JavaSE,数据结构领域博主 专栏&#xff1a;JavaSE 作者介绍&#xff1a;大三学生&#xff0c;希望一起进步~ 文章目录 目录 文章目录 一、异常结构体系 二、异常分类 三、异常处理 3.1异常抛出 3.2 异常捕获 四.【面试题】 五、题目练习…
阅读更多...
Consensus Algorithm -- Raft

Consensus Algorithm -- Raft

The Raft Consensus Algorithm Go 实现&#xff1a;etcd/raft、dragonboat Rust 实现&#xff1a;TiKV C 实现 &#xff1a;nebula-graph-storage、 RethinkDB、logcabin 拜占庭将军问题 拜占庭将军问题&#xff08;Byzantine failures&#xff09;&#xff0c;是由莱斯利兰…
阅读更多...
ResT: An Efficient Transformer for Visual Recognition

ResT: An Efficient Transformer for Visual Recognition

文章地址: https://arxiv.org/pdf/2105.13677.pdf codeResT: An Efficient Transformer for Visual Recognition一、引言二、ResT一、Transformer模块的再思考二、Efficient Transformer Block三、Patch Embedding四、Positional Encoding五、整体架构三、实验一、分类二、目标…
阅读更多...
最新文章

Copyright @ 2022~2023