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

        树状数组(Binary Index Tree, BIT),是一种一般用来处理单点修改区间求和操作类型的题目的数据结构,时间复杂度为O(log n)。

        对于普通数组来说,单点修改的时间复杂度是 O(1),但区间求和的时间复杂度是 O(n) 。如果使用前缀和数组呢?区间求和的时间复杂度降低为O(1),但是单点修改又会变为O(n) 。那么,我们能不能找到一种数组,中和两者的时间复杂度都不那么高?

        树状数组就是这么一种结构,它通过二进制来划分区间,例如我们要求出前13项的和,13的二进制表示为(1101),接着分别查询((0000), (1000)],((1000), (1100)],和((1100), (1101)]的和并相加。

        上述区间的划分规则是将13不断减去最低位的1来划分的,这里就需要用的之前学过的lowbit(),acwing基础课——位运算_acwing位运算_我的鱼干呢w的博客-CSDN博客可从这里学习lowbit()的用法和实现。

        树状数组的大致结构如下:

        通过树状数组,我们需要更新的区间至多不会超过log~2~N,这样我们就能以O(log n)的时间复杂度完成单点修改和区间查询。下面给出树状数组的实现:

//单点修改
void modify(int k, int x)
{
    for(int i = k; i <= n; i += lowbit(i)) tr[i] += x;
}
//统计前x项的和
int count(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

//区间求和
int query(int a, int b)
{
    return count(b) - count(a - 1);
}

来到例题练练手吧!

241. 楼兰图腾 - AcWing题库

在完成了分配任务之后,西部 314 来到了楼兰古城的西部。

相传很久以前这片土地上(比楼兰古城还早)生活着两个部落,一个部落崇拜尖刀(V),一个部落崇拜铁锹(),他们分别用 V 和  的形状来代表各自部落的图腾。

西部 314 在楼兰古城的下面发现了一幅巨大的壁画,壁画上被标记出了 n 个点,经测量发现这 n 个点的水平位置和竖直位置是两两不同的。

西部 314 认为这幅壁画所包含的信息与这 n 个点的相对位置有关,因此不妨设坐标分别为 (1,y1),(2,y2),…,(n,yn)其中 y1∼yn 是 1 到 n 的一个排列。

西部 314 打算研究这幅壁画中包含着多少个图腾。

如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n 且 yi>yj,yj<yk,则称这三个点构成 V 图腾;

如果三个点 (i,yi),(j,yj),(k,yk) 满足 1≤i<j<k≤n 且 yi<yj,yj>y,则称这三个点构成  图腾;

西部 314 想知道,这 n 个点中两个部落图腾的数目。

因此,你需要编写一个程序来求出 V 的个数和  的个数。

输入格式

第一行一个数 n。

第二行是 n 个数,分别代表 y1,y2,…,yn。

输出格式

两个数,中间用空格隔开,依次为 V 的个数和  的个数。

数据范围

对于所有数据,n≤200000,且输出答案不会超过 int64。
y1∼yn 是 1 到 n 的一个排列。

输入样例:
5
1 5 3 2 4
输出样例:
3 4
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 200010;

int n;
int a[N];
int tr[N];
int Greator[N], Lower[N];

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

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

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 u = a[i];
        Greator[i] = sum(n) - sum(u);
        Lower[i] = sum(u - 1);
        add(u, 1);
    }
    
    memset(tr, 0, sizeof tr);
    
    LL res1 = 0, res2 = 0;
    for(int i = n; i; i -- )
    {
        int u = a[i];
        res1 += (LL)Greator[i] * (sum(n) - sum(u));
        res2 += (LL)Lower[i] * sum(u - 1);
        add(u, 1);
    }
    
    cout << res1 << " " << res2;
    
    return 0;
}

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

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

相关文章

【创作活动】作为程序员的那些愚蠢瞬间

作为一名程序员&#xff0c;我相信你一定遇到过这种情况&#xff1a;在写代码的时候&#xff0c;遇到了一些bug&#xff0c;在当下怎么检查都查不出问题出现在哪&#xff0c;等过几天后突然发现困扰自己的问题原来这么简单&#xff0c;突然觉得自己很蠢。这种情况在我身上也发生…

人工智能-深度学习之序列模型

想象一下有人正在看网飞&#xff08;Netflix&#xff0c;一个国外的视频网站&#xff09;上的电影。 一名忠实的用户会对每一部电影都给出评价&#xff0c; 毕竟一部好电影需要更多的支持和认可。 然而事实证明&#xff0c;事情并不那么简单。 随着时间的推移&#xff0c;人们对…

漏洞分析 | 漏洞调试的捷径:精简代码加速分析与利用

0x01前言 近期&#xff0c;Microsoft威胁情报团队曝光了DEV-0950&#xff08;Lace Tempest&#xff09;组织利用SysAid的事件。随后&#xff0c;SysAid安全团队迅速启动了应急响应&#xff0c;以应对该组织的攻击手法。然而&#xff0c;在对漏洞的分析和复现过程中&#xff0c…

使用Microsoft Dynamics AX 2012 - 1. 什么是Microsoft Dynamics AX?

Dynamics AX是Microsoft的核心业务管理解决方案&#xff0c;旨在满足中型公司和跨国组织的要求。基于 DynamicsAX基于最先进的体系结构和深度集成&#xff0c;在确保高可用性的同时&#xff0c;展现了全面的功能。 在AX 2012版中&#xff0c;Dynamics AX显示了大量新功能和增强…

Postman内置动态参数以及自定义的动态参数

近期在复习Postman的基础知识&#xff0c;在小破站上跟着百里老师系统复习了一遍&#xff0c;也做了一些笔记&#xff0c;希望可以给大家一点点启发。 一&#xff09;内置动态参数 {{$timestamp}} 生成当前时间的时间戳{{$randomInt}} 生成0-1000之间的随机数{{$guid}} 生成随…

⑩【MySQL】存储引擎详解, InnoDB、MyISAM、Memory。

个人简介&#xff1a;Java领域新星创作者&#xff1b;阿里云技术博主、星级博主、专家博主&#xff1b;正在Java学习的路上摸爬滚打&#xff0c;记录学习的过程~ 个人主页&#xff1a;.29.的博客 学习社区&#xff1a;进去逛一逛~ 存储引擎 ⑩【MySQL存储引擎】1. MySQL体系结构…

隐私协议 Secret Network 宣布使用 Octopus Network 构建的 NEAR-IBC 连接 NEAR 生态

2023年11月 NearCon2023 活动期间&#xff0c;基于 Cosmos SDK 构建的隐私协议 Secret Network&#xff0c;宣布使用 Octopus Network 开发的 NEAR-IBC&#xff0c;于2024年第一季度实现 Secret Network 与 NEAR Protocol 之间的跨链交互。 这将会是Cosmos 生态与 NEAR 之间的首…

java VR全景商城免费搭建 saas商城 b2b2c商城 o2o商城 积分商城 秒杀商城 拼团商城 分销商城 短视频商城

1. 涉及平台 平台管理、商家端&#xff08;PC端、手机端&#xff09;、买家平台&#xff08;H5/公众号、小程序、APP端&#xff08;IOS/Android&#xff09;、微服务平台&#xff08;业务服务&#xff09; 2. 核心架构 Spring Cloud、Spring Boot、Mybatis、Redis 3. 前端框架…

一个开源的汽修rbac后台管理系统项目,基于若依框架,实现了activiti工作流,附源码

文章目录 前言&源码项目参考图&#xff1a; e店邦O2O平台项目总结一、springboot1.1、springboot自动配置原理1.2、springboot优缺点1.3、springboot注解 二、rbac2.1、概括2.2、三个元素的理解 三、数据字典3.1、概括与作用3.2、怎么设计3.3、若依中使用字典 四、工作流—…

STM32CubeIDE报“xxx is not implemented and will always fail”解决方法

本文介绍STM32CubeIDE报“xxx is not implemented and will always fail”解决方法。 最近用STM32CubeIDE开发STM32程序时&#xff0c;编译报警告&#xff1a; warning: _close is not implemented and will always fail warning: _lseek is not implemented and will always…

idea中把spring boot项目打成jar包

打jar包 打开项目&#xff0c;右击项目选中Open Module Settings进入project Structure 选中Artifacts&#xff0c;点击中间的加号&#xff08;Project Settings->Artifacts->JAR->From modules with dependencies &#xff09; 弹出Create JAR from Modules&#…

想转行互联网行业,是选择网络安全还是人工智能?

随着数字时代的到来&#xff0c;网络安全和人工智能成了科技创新产业的重要组成部分。也逐渐成了大多数人心中热门的行业选择。那么该如何抉择呢&#xff1f; 首先我们来了解下人工智能的发展前景&#xff1a; 如今&#xff0c;人工智能技术无论是在核心技术方面&#xff0c…

系列四、本地接口(Native Interface)

一、概述 本地接口的作用是融合不同的编程语言为Java所用&#xff0c;它的初衷是融合C/C程序&#xff0c;Java诞生的时候正是C/C横行的时候&#xff0c;要想立足&#xff0c;必须要调用C/C的程序&#xff0c;于是Java就在内存中开辟了一块区域专门用于处理标记为native的代码&a…

wpf devexpress数据统计

GridControl允许显示总结信息关于单个数据行分组。例如&#xff0c;你可以显示记录数量&#xff0c;最小和最大值。这个统计信息可以叫做数据统计。 创建统计 GridControl 支持总结和分组统计&#xff1a; 总结统计 - 一个总结函数值计算对于所有列和视图显示统计面板和固定统…

2023最受推荐的五款项目管理工具

1、进度猫 进度猫是国内一款轻量级项目管理工具&#xff0c;适用于实时协作的团队。 以甘特图为向导&#xff0c;基于任务清单todolist&#xff0c;支持多用户协作&#xff1b; 甘特图显示具体任务清单、时间和任务的进度&#xff1b; 对未完成任务、已完成任务进行分类管…

深度学习OCR中文识别 - opencv python 计算机竞赛

文章目录 0 前言1 课题背景2 实现效果3 文本区域检测网络-CTPN4 文本识别网络-CRNN5 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习OCR中文识别系统 ** 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;…

【Spring进阶系列丨第二篇】Spring中的两大核心技术IoC(控制反转)与DI(依赖注入)

前言 我们都知道Spring 框架主要的优势是在 简化开发 和 框架整合 上&#xff0c;至于如何实现就是我们要学习Spring 框架的主要内容&#xff0c;今天我们就来一起学习Spring中的两大核心技术IoC&#xff08;控制反转&#xff09;与DI&#xff08;依赖注入&#xff09;。 文章目…

【BIM入门实战】高程点无法放置的解决方法

文章目录 一、问题提出二、解决办法1. 检查模型图形样式2. 高程点可以放置的图元一、问题提出 在平面图中添加高程点时有时会遇到无法在楼板等平面构件上放置高程点,应如何设置才能使高程点正常放置? 如下图所示,楼板上无法放置高程点: 二、解决办法 1. 检查模型图形样式…

Linux C/C++全栈开发知识图谱(后端/音视频/游戏/嵌入式/高性能网络/存储/基础架构/安全)

众所周知&#xff0c;在所有的编程语言中&#xff0c;C语言是一门颇具学习难度&#xff0c;需要很长学习周期的编程语言。甚至很多人经常听到一句调侃的话语——“C&#xff0c;从入门到放弃”。 C界的知名书籍特别多&#xff0c;从简单到高端书籍&#xff0c;许多书籍都是C之…

1.mysql安装及基础

目录 概述安装上传jar包解压添加用户组和用户更改权限修改配置文件 my.cnf初始化登录mysql修改密码远程登录生效配置 sql语句分类数据定义语言 结束 概述 mysql安装及基础&#xff0c;后续涉及基础会继续补充。 安装 上传jar包 下载地址 解压 tar -zxvf mysql-5.7.44-li…