高级数据结构—树状数组

引入问题:

给出一个长度为n的数组,完成以下两种操作:
1. 将第i个数加上k

2. 输出区间[i,j]内每个数的和

朴素算法:

单点修改:O( 1 )

区间查询:O( n )

使用树状数组:

单点修改:O( logn )

区间查询:O( logn )

前置知识:

lowbit()
运算:非负整数x在二进制表示下最低位1及其后面的0构成的数值。

如lowbit(12)= 1100 = 4

函数实现: 

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

树状数组思想:

树状数组的主要思想就是利用树结构维护“前缀和”。

对于一个序列,对其建立如下树形结构:

1.每个结点t[x]保存以x为根的子树中叶结点值的和
2.每个结点覆盖的长度为lowbit(x)
3.t[x]结点的父结点为t[x + lowbit(x)]
4.树的深度为log2n+1

树状数组操作:

add(x, k)表示将序列中第x个数加上k。

在整棵树上维护这个值,需要一层一层向上找到父结点,并将这些结点上的t[x]值都加上k,这样保证计算区间和时的结果正确。

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

ask(x)表示将查询序列前x个数的和

以ask(7)为例:
查询这个点的前缀和,需要从这个点向左上找到上一个结点,将加上其结点的值。向左上找到上一个结点,只需要将下标 x -= lowbit(x),例如 7 - lowbit(7) = 6

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

例题: 

楼兰图腾

题目链接:楼兰图腾

从左向右依次遍历每个数a[i],使用树状数组统计在i位置之前所有比a[i]大的数的个数、以及比a[i]小的数的个数。
统计完成后,将a[i]加入到树状数组。

从右向左依次遍历每个数a[i],使用树状数组统计在i位置之后所有比a[i]大的数的个数、以及比a[i]小的数的个数。
统计完成后,将a[i]加入到树状数组。

代码附上:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+5;
int tr[N];
int low[N],great[N];
int a[N];
int 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;
	}
	return;
}

int ask(int x){
	int res=0;
	for(int i=x;i>=1;i-=lowbit(i)){
		res+=tr[i];
	}
	return res;
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];

	for(int i=1;i<=n;i++){//记录i点左边的信息
		int y=a[i];
		low[i]=ask(y-1);//low[i]记录左边[1,y-1]区间的数字个数
		great[i]=ask(n)-ask(y);//great[i]记录左边[y+1,n]区间的数字个数
		add(y,1);//加入树状数组中,出现一次+1
	}

	memset(tr,0,sizeof(tr));//初始化
	int ans1=0,ans2=0;

	for(int i=n;i>=1;i--){//记录i点右边的信息
		int y=a[i];
		ans2+=low[i]*ask(y-1);//乘法原理
		ans1+=great[i]*(ask(n)-ask(y-1));
		add(y,1);
	}

	cout<<ans1<<" "<<ans2<<"\n";

	return 0;
}

一个简单的整数问题

题目链接:一个简单的整数问题

区间修改 + 求单点

那么这道题目可以采用差分的方法去做,在上一道题目中我们求的是区间和,采用前缀和的思想去做,那么这里我们可以把单点a[i]看成前缀和,因为a[i]=\sum差分和。

首先我们要先建差分数组:

for(int i=1;i<=n;i++){
        add(i,a[i]-a[i-1]);
    }

 那么接下来的情况就跟第一题一样了

代码附上:

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N =1e5+5;
int a[N],tr[N],low[N],great[N];
int n,q;

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;
    }
    return;
}

int ask(int x){
    int res=0;
    for(int i=x;i>=1;i-=lowbit(i)){
        res+=tr[i];
    }
    return res;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++){
        add(i,a[i]-a[i-1]);
    }

    while(q--){
        char op;cin>>op;
        if(op=='C'){
            int l,r,d;cin>>l>>r>>d;
            add(l,d);
            add(r+1,-d);
        }
        else if(op=='Q'){
            int l;cin>>l;
            cout<<ask(l)<<"\n";
        }
    }

    return 0;
}

一个简单的整数问题2

题目链接:一个简单的整数问题2

区间查询+区间修改

直接上图:

 所以这道题目我们需要维护两个树状数组,一个是d[i],另一个是i*d[i]。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int n,m;
int a[N];
int tr[N],tr2[N];
//tr[]数组是原始数组的差分数组d[i]的树状数组
//tr2[]数组是原始数组的差分数组乘以i即i*d[i]的树状数组

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

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

void add2(int x,int c){
    for(int i=x;i<=n;i+=lowbit(i)){
        tr2[i]+=c;
    }
    return;
}

int ask1(int x){
    int res=0;
    for(int i=x;i>=1;i-=lowbit(i)){
        res+=tr[i];
    }
    return res;
}

int ask2(int x){
    int res=0;
    for(int i=x;i>=1;i-=lowbit(i)){
        res+=tr2[i];
    }
    return res;
}

int get_sum(int x){//最后一步的推导
    return ask1(x)*(x+1)-ask2(x);
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    memset(tr2,0,sizeof(tr2));
    memset(tr,0,sizeof(tr));
    for(int i=1;i<=n;i++)cin>>a[i];

    for(int i=1;i<=n;i++){
        int b=a[i]-a[i-1];
        add1(i,b);
        add2(i,b*i);
    }

    while(m--){
        char op;cin>>op;
        if(op=='Q'){
            int l,r;cin>>l>>r;
            cout<<get_sum(r)-get_sum(l-1)<<"\n";
        }
        else if(op=='C'){
            int l,r,d;cin>>l>>r>>d;
            add1(l,d),add1(r+1,-d);
            add2(l,l*d),add2(r+1,(r+1)*(-d));
        }
    }

    return 0;
}

谜一样的牛

题目链接:谜一样的牛

仅仅根据题目的信息,很难找出他们之间的高度关系。面对这种题目,我们可以从边界去思考,(正着不行就反着来),从最后一头牛看,最后一头牛的a[i]表示前i头牛有x个比它矮的,那么也就意味着它排第x+1位,那么从倒数第二头牛来看,前面有y头比它矮的,那最后一头牛可能比它高也可能比它矮,因此,对于倒数第二头牛而言,它应该在除去上述x+1的区间[1,n]中,选取A(n−1)+1小的数。其他的牛以此类推。

假如建立一个全部元素为1的数列,某个位置的数为1代表这个高度还不知道是哪头牛的,那么就用树状数组维护该数列的前缀和,若某个位置的前缀和等于A(i)+1此时的下标就是要找的数。选择这个数后,将相应位置的1置0.可以二分这个位置。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+5;
int a[N],ans[N],tr[N];
int 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;
	}	
	return;
}

int ask(int x){
	int res=0;
	for(int i=x;i>=1;i-=lowbit(i)){
		res+=tr[i];
	}
	return res;
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
	a[1]=0;
	for(int i=2;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)tr[i]=lowbit(i);//初始化

	for(int i=n;i>=1;i--){//从后往前枚举
		int k=a[i]+1;//找剩余的牛中高度排第k
		int l=1,r=n;
		while(l<r){
			int mid=(l+r)/2;
			if(ask(mid)>=k)r=mid;
			else l=mid+1;
		}
		ans[i]=r;
		add(r,-1);//高度排第r的牛去掉
	}

	for(int i=1;i<=n;i++){
		cout<<ans[i]<<"\n";
	}

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/564061.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

文档分享怎么用二维码?扫码获得文档的制作方法

现在日常工作和生活中&#xff0c;经常会看到可以用于展示文件的二维码图片&#xff0c;使用这种方式可以向其他人传递一些资料、通知、数据等情况。比如常见的内容有企业介绍、产品内容、使用说明、活动流程等类型的内容&#xff0c;那么这些不同类型的文件该如何制作二维码呢…

医学图像三维重建与可视化系统 医学图像分割 区域增长

医学图像的三维重建与可视化&#xff0c;这是一个非常有趣且具有挑战性的课题&#xff01;在这样的项目中&#xff0c;可以探索不同的医学图像技术&#xff0c;比如MRI、CT扫描等&#xff0c;然后利用这些图像数据进行三维重建&#xff0c;并将其可视化以供医生或研究人员使用。…

el-select多选非空校验

一、首先是前端版本&#xff08;不建立在版本上的bug修改就是耍流氓&#xff01;&#xff09;&#xff1a; 二、原来页面是下拉单选&#xff0c;新需求要改成下拉多选&#xff0c;改成多选后就发现非空校验失效了。 三、el-select多选&#xff0c;绑定v-model的就是一个数组了…

Unity导出package

C#代码导出后为一个dll&#xff0c;原有的不同平台的库不变。 以下操作均在build PC 平台下操作。 1.在要导出的文件夹下建assembly definition (Any platform) 2.将项目文件夹下的\Library\ScriptAssemblies中的相应assembly definition的dll复制到要导出的文件夹下 3.在uni…

【ES】springboot集成ES

1. 去Spring官方文档确认版本兼容性 这一版的文档里没有给出springboot的版本对应&#xff0c;但我在一个博主的文章里看到的es8.0以前的官方文档中就有给出来&#xff0c;所以还需要再去寻找spring framework和springboot的对应关系&#xff1f;&#xff1f;&#xff1f; 还…

17-软件脉冲宽度调制(SW_PWM)

ESP32-S3的软件脉冲宽度调制&#xff08;SW_PWM&#xff09; 引言 ESP32-S3 LED 控制器LEDC 主要用于控制 LED&#xff0c;也可产生PWM信号用于其他设备的控制。该控制器有 8 路通道&#xff0c;可以产生独立的波形&#xff0c;驱动 RGB LED 等设备。LED PWM 控制器可在无需C…

227基于matlab的作业调度问题

基于matlab的作业调度问题。采用遗传算法&#xff0c;解决作业调度问题。一共三个作业&#xff0c;每个作业有不同的时间长度和紧急程度&#xff0c;超过时间会有惩罚措施。通过遗传算法计算出最好的作业安排&#xff0c;使得惩罚最小&#xff0c;获益最大。最终结果通过GUI用甘…

JavaScript 数据类型 对象概述

对象代表两个人&#xff0c;一个是你和你的对象&#xff0c;对于程序来说也是这个样子&#xff0c;一个键&#xff0c;一个值组成。 什么是对象?对象(object)是JavaScript语言的核心概念&#xff0c;也是最重要的数据类型简单说&#xff0c;对象就是一组“键值对”(key-value…

DC学习笔记

视频 数字逻辑综合工具实践 DC 01_哔哩哔哩_bilibili 一、DC工作模式&#xff08;此小节为搬运内容&#xff09; 原链接&#xff1a;Design_Compiler User Guide 随手笔记&#xff08;9&#xff09;Using Floorplan Information - 知乎 DC拥有四种工作模式&#xff1a; 工…

SQL优化——全自动SQL审核

文章目录 1、抓出外键没创建索引的表2、抓出需要收集直方图的列3、抓出必须创建索引的列4、抓出SELECT * 的SQL5、抓出有标量子查询的SQL6、抓出带有自定义函数的SQL7、抓出表被多次反复调用SQL8、抓出走了FILTER的SQL9、抓出返回行数较多的嵌套循环SQL10、抓出NL被驱动表走了全…

vue3的getCurrentInstance获取当前组件实例

vue3的setup中没有this时需要使用getCurrentInstance()来获取。 在 Vue 3 中&#xff0c;getCurrentInstance 方法可以在组合式 API&#xff08;Composition API&#xff09;中获取当前组件实例。这个方法返回一个包含了组件实例的对象&#xff0c;你可以用它来访问组件的 pro…

【刷题】代码随想录算法训练营第二十天|654、最大二叉树,617、合并二叉树,700、二叉搜索树中的搜索,98、验证二叉搜索树

目录 654、最大二叉树617、合并二叉树700、二叉搜索树中的搜索98、验证二叉搜索树 654、最大二叉树 讲解&#xff1a;https://programmercarl.com/0654.%E6%9C%80%E5%A4%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html 最大二叉树的规则&#xff1a; 二叉树的根是数组中的最大元素。左子…

电商数据采集API接口系列|请求示例测试方式丨商品详情,详情图,sku价格等

电商数据采集API接口系列是用于从电商平台收集各种商品信息的工具&#xff0c;包括商品详情、详情图、SKU价格等。以下是一般情况下使用电商API接口进行数据采集的步骤和测试方式&#xff1a; 1.请求方式&#xff1a;HTTP POST GET &#xff08;复制薇&#xff1a;Anzexi58 获…

VS安装教程

文章目录 VS安装步骤 VS安装步骤 &#xff08;1&#xff09; 下载VS2022社区版&#xff08;根据情况选择自己需要的版本下载&#xff09;&#xff0c;下载的方式&#xff0c;可以通过微软官方下载。https://visualstudio.microsoft.com/zh-hans/downloads/?cidlearn-onpage-d…

uniapp——授权报错,选择合适的基础库

说明 我的小程序开发版本点击选择头像报错 更换基础库就好了

4.9 启动系统任务❤❤❤

有一些特殊的任务需要在系统启动时执行&#xff0c;例如配置文件加载、数据库初始化等操作。 Spring Boot对此提供了两种解决方案&#xff1a;CommandLineRunner和ApplicationRunner。 CommandLineRunner和ApplicationRunner基本一致&#xff0c;差别主要体现在参数上。 1. Co…

vue详解(3)

1. Vue 生命周期总结 四个阶段&#xff0c;八个钩子 -> 三个常用 created&#xff0c;mounted&#xff0c;beforeDestroy 2. 工程化开发 & 脚手架 Vue CLI 基本介绍&#xff1a; Vue CLI 是 Vue 官方提供的一个全局命令工具。 可以帮助我们快速创建一个开发 Vue 项目…

基于深度学习的脑部肿瘤检测系统

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长 QQ 名片 :) 1. 项目简介 当大脑中形成异常细胞时&#xff0c;就会发生脑肿瘤。肿瘤主要有两种类型&#xff1a;癌性&#xff08;恶性&#xff09;肿瘤和良性肿瘤。恶性肿瘤可分为原发性肿瘤和继发性肿瘤&#xff0c;前者始…

单片机STM32中断与事件的区别

【转】1-单片机STM32---中断与事件的区别 - Engraver - 博客园 (cnblogs.com) 路径不同&#xff0c;处理方式不同&#xff0c;是否有程序不同&#xff0c;是否有cpu参与不同。 事件是比中断更新的升级产物。

Golang | Leetcode Golang题解之第41题缺失的第一个正数

题目&#xff1a; 题解&#xff1a; func firstMissingPositive(nums []int) int {n : len(nums)for i : 0; i < n; i {for nums[i] > 0 && nums[i] < n && nums[nums[i]-1] ! nums[i] {nums[nums[i]-1], nums[i] nums[i], nums[nums[i]-1]}}for i …