不仅是拼多多,该题还在诸如 神州信息 和 滴滴出行 这样的互联网大厂笔试中出现过:
给定 n 个数组成的一个数列,规定有两种操作,一是修改某个元素,二是求子数列[a,b]的连续和。
大家好,今天给大家介绍一种新的非常非常实用的数据结构。大家学会了之后,应对各大公司的面试题以及LeetCode等网站的刷题都会用得到,也是广大acmer的入门数据结构之一。
题意:找出所有区间和在某个范围之内的个数 题解:区间问题用线段树来做。首先n^2 可以遍历所有的区间,这样会超时。 我们用线段树,期望可以在遍历整个线段树的过程中把问题解决掉,遍历整个线段树的效率是O(n*logn) 如果遍历每个节点上的区间上所花的时间是n*logn,也可以接受,总的效率就是O(n*logn*logn) 线段树每个节点,存储这个区间的前缀区间和,和后缀区间和,而且要是排好序的。 父节点的区间个数,需要计算它的两个子节点中,左子节点的后缀区间和
☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆ ☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆ ☆ミヾ(∇≦((ヾ(≧∇≦)〃))≧∇)ノ彡☆
如果对这个数据进行模拟操作,最差时间复杂度可能为O(mn) , 如果数据量非常大,处理起来非常容易超时。所以采用一种数据结构来优化。所以线段树就诞生了。
由于有些读者朋友私聊我,希望出几期基础算法的讲解,kmp,dp,哈希,搜索,贪心等对初学者还是不太友好,所以我打算更新几期基础算法合集,没办法谁让我宠粉丝呢?彦祖,热巴说你呢,快关注!
线段树算是比较难的一个数据结构,当时我高中提高组就没学懂,细数我学线段树也学了4遍,最早学的时候一脸懵逼,最近在刷题中发现其在蓝桥杯中也有考察,就寻思写一篇博客来巩固。
今天我们照惯例来看下LeetCode周赛,这一场的比赛由普渡机器人赞助,前300名的同学可以获得内推机会。
输入一个含有 n(1≤n≤100000) 个非负整数的 a 数组和一个 1~n 的排列 p 数组,求每次删除 a[p[i]] 后,最大连续子段和(不能跨越被删除的)是多少?
线段树可以做很多事情,树状数组能做的线段树都能够实现。原理上线段树是一个非常简单的数据结构,但是在代码上比树状数组麻烦。线段树和树状数组都是维护一个序列,但是线段树可以进行的操作有很多,基本没有什么限制,不仅仅可以做单点,还可以做比如“区间的最大值”、“区间减法”、“染色”、“区间面积”、“长度”、“最大连续和”等等。
树状数组的核心函数lowbit(int m):作用是求出 m 的二进制表示的末尾1的位置,对于要查询 m 的前缀和,m = m - lowbit(m) 代表不断对二进制末尾1进行-1操作,不断执行直到 m == 0 结束,就能得到前缀和由哪几个Cm构成
设sum[i]=sum[i-1]+f[i](1<i≤n,sum[1]=f[1]=d[1]=a[1])。
无递归,不算法。无论怎样强调递归的重要性,都不为过。受限于计算机的思维能力,计算机的计算找答案的过程就是在不停试错、纠正错误的过程,类似于爱迪生发明灯炮。递归能帮助我们在不知道计算边界的情形下试错。
A. Floor Number ---- Origional Link 题目大意: 给定目标房间编号 n 及一层楼住户数量 x。 第一层楼只有 2 个住户,求目标房间所在楼层。 ---- 思想: 签到题。 n\le2 时在第一层。 n\gt 2 时: 若 x 可以整除 n-2,则在 \frac{n-2}{m} + 1 层; 反之在 \frac{n-2}{m} + 2 层。 ---- 代码: #include <iostream> #include <cstring> #include <cstdio
Best Cow Fences Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 10174 Accepted: 3294 Description Farmer John’s farm consists of a long row of N (1 <= N <= 100,000)fields. Each field contains a certain number of cows, 1 <= ncows
给你三个字符串s1,s2,s3 问你s3是否由s1和s2互相交叉组成。也就是说s3中的某个子序列是s1,剩下的字符串组成s2。
首先,离散化是指数值域非常大,例如 ,但是个数相对较少,例如只有 个, 但在我们的程序中需要通过这些数值作为下标,且依赖的是这些数值之间的顺序关系(当然通常这些数是有序的)。如果为了这 个数而开一个 的数组过于浪费空间,因此我们可以采用离散化的方法,将这些数映射到 上,这个过程就叫做离散化。
C. Vasya and Golden Ticket time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Recently Vasya found a golden ticket — a sequence which consists of n digits a1a2…an. Vasya considers a ticket to be lucky if it can be divided into two or more non-intersecting segments with equal sums. For example, ticket 350178 is lucky since it can be divided into three segments 350, 17 and 8: 3+5+0=1+7=8. Note that each digit of sequence should belong to exactly one segment.
【题目】给你两个非负整数 low 和 high 。请你返回 low 和 high 之间(包括二者)奇数的数目。
查询也是一个递归的过程,如果查询的区间已经把当前区间完全包含了,则可以返回该区间了。
线段树是一个复杂的数据结构,比较难理解,也比较难解释清楚。在我将这个数据结构反复学习了五遍的时候,我终于有了信心写出这篇介绍线段树的文章。希望大家能够掌握这种数据结构。
样例解释:第 1 到第 4 个数加起来和为 10。第 2 个数到第 3 个数加起来和为5。
接下来m行,每行3个整数p,x,y,p表示操作类型,p=1时表示修改格子x的权值为y,p=2时表示求区间[x,y]内格子权值和,p=3时表示求区间[x,y]内格子最大的权值。
题意应该很好理解,其实就是给了很多个区间,求对于每一个区间,它属于多少个区间的真子集。例如下面的红色区间,被两个蓝色区间真包含。
子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
线段树是一种专用于处理区间查询的数据结构,在解决范围内的查询和更新操作时具有高效性能。在本文中,我们将深入讲解Python中的线段树,包括线段树的基本概念、构建、查询和更新操作,并使用代码示例演示线段树的使用。
题目链接:P3128 [USACO15DEC] Max Flow P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
刚学了线段树,趁现在理解比较清楚,写篇博客供以后翻阅,线段树有很多应用,如求区间总和,最大值,最小值等,总之求区间问题都可以想想线段树,这里以求和为例
本文摘自清北OI学堂内部笔记,作者潘恺璠,来自柳铁一中曾参加过清北训练营提高组精英班,主要记录的是信息学基础算法。笔记非常详细,特分享给大家! NOIP2019年夏令营正在报名中,6大校区10种班型,可前往微信noipnoi报名!
利用单调栈,从前向后和从后向前分别遍历一遍数组,得到每个元素的左边界和右边界(边界的定义即为碰到比该元素更小的即停止),最后用每个元素乘以每个元素对应的区间和,找出最大值即可。这里有一个技巧,为了防止每个元素重复计算一段区间和,可以提前开一个递增序列,用于保存某元素之前的各项和(含该元素),求取一段区间和的时候用右边界的递增和减去左边界减一的递增和即可。
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ,其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
在定义了val变量的代码块执行期间,val变量只能进行唯一一次初始化。但是,如果编译器能确保只有唯一一条初始化语句被执行,可以根据条件使用不同的值来初始化它:
前面发过 几个视频,也算是对视频剪辑入了个门。像我这种非专业剪辑玩家,不做什么宏大特效电影镜头,只是做个视频教程,其实也没啥难度,只需要把视频剪流畅,所以用到最多的功能就是切割功能,然后删除和拼接视频片接。
历史上最早的科学家曾经不承认实验可以有误差,认为所有的测量都必须是精确的,把任何误差都归于错误。后来人们才慢慢意识到误差永远存在,而且不可避免。即使实验条件再精确也无法完全避免随机干扰的影响,所以做科学实验往往要测量多次,用取平均值之类的统计手段去得出结果。
当需要其他位置上的值时,我们通过 “任意整数可以表示成若干个 2 的次幂项的和” 这一性质,使用之前求出的代表值拼成所需的值
对于一个给定的数组或序列,我们定义前缀和数组prefixSum,其中prefixSum[i]表示原数组中前i个元素的和。即prefixSum[i] = nums[0] + nums[1] + ... + nums[i-1]。特别地,prefixSum[0] = 0。
对于非专业剪辑玩家,不做什么宏大特效电影镜头,只是做个视频教程,其实也没啥难度,只需要把视频剪流畅,所以用到最多的功能就是切割功能,然后删除和拼接视频片接。 没有剪过视频的读者可能不知道,在常用的剪辑软件中视频被切割成若干片段之后,每个片段都可以还原成原始视频。 就比如一个 10 秒的视频,在中间切一刀剪成两个 5 秒的视频,这两个五秒的视频各自都可以还原成 10 秒的原视频。就好像蚯蚓,把自己切成 4 段就能搓麻,把自己切成 11 段就可以凑一个足球队。 剪视频时,每个视频片段都可以抽象成了一个个区间
求[min((Z+L)%N,(Z+R)%N)+1,max((Z+L)%N,(Z+R)%N)+1]中不同前缀的个数,Z是上次询问的结果,N是字符串总个数。Q次询问。
Tag : 「枚举」、「哈希表」、「排序」、「前缀和」、「二分」、「滑动窗口」、「双指针」
给定一个整数数组 nums,返回区间和在 [lower, upper] 之间的个数,包含 lower 和 upper。
Apple Tree Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 22613 Accepted: 6875 Description There is an apple tree outside of kaka’s house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he
b≠0,f为二次函数,最大值点在区间端点或者x0=c/(2*b),当L≤x0≤R时,ans=max{f(L),f(R),f(x0)}。
树状数组(Binary Indexed Tree(BIT), Fenwick Tree)是一个查询和修改复杂度都为log(n)的数据结构。主要用于查询任意两位之间的所有元素之和,但是每次只能修改一个元素的值;经过简单修改可以在log(n)的复杂度下进行范围修改,但是这时只能查询其中一个元素的值(如果加入多个辅助数组则可以实现区间修改与区间查询)。 百度上给出了令人难以理解的概念,其实这个东西我也是琢磨了一天,参考了大量博客的笔记才搞清楚了大致思路和原理,说说心得吧! 假设数组a[1..n],那么查询a[1]
(注:由于线段树的每个节点代表一个区间,以下叙述中不区分节点和区间,只是根据语境需要,选择合适的词) 线段树本质上是维护下标为1,2,…,n的n个按顺序排列的数的信息,所以,其实是“点树”,是维护n的点的信息,至于每个点的数据的含义可以有很多, 在对线段操作的线段树中,每个点代表一条线段,在用线段树维护数列信息的时候,每个点代表一个数,但本质上都是每个点代表一个数。以下,在讨论线段树的时候,区间[L,R]指的是下标从L到R的这(R-L+1)个数,而不是指一条连续的线段。只是有时候这些数代表实际上一条线段的统计结果而已。
领取专属 10元无门槛券
手把手带您无忧上云