这段时间我会把蓝桥杯官网上的所有非VIP题目都发布一遍，让大家方便去搜索，所有题目都会有几种语言的写法，帮助大家提供一个思路，当然，思路只是思路，千万别只看着答案就认为会了啊，这个方法基本上很难让你成长，成长是在思考的过程中找寻到自己的那个解题思路，并且首先肯定要依靠于题海战术来让自己的解题思维进行一定量的训练，如果没有这个量变到质变的过程你会发现对于相对需要思考的题目你解决的速度就会非常慢，这个思维过程甚至没有纸笔的绘制你根本无法在大脑中勾勒出来，所以我们前期学习的时候是学习别人的思路通过自己的方式转换思维变成自己的模式，说着听绕口，但是就是靠量来堆叠思维方式，刷题方案自主定义的话肯定就是从非常简单的开始，稍微对数据结构有一定的理解，暴力、二分法等等，一步步的成长，数据结构很多，一般也就几种啊，线性表、树、图、再就是其它了。顺序表与链表也就是线性表，当然栈，队列还有串都是属于线性表的，这个我就不在这里一一细分了，相对来说都要慢慢来一个个搞定的。蓝桥杯中对于大专来说相对是比较友好的，例如三分枚举、离散化，图，复杂数据结构还有统计都是不考的，我们找简单题刷个一两百，然后再进行中等题目的训练，当我们掌握深度搜索与广度搜索后再往动态规划上靠一靠，慢慢的就会掌握各种规律，有了规律就能大胆的长一些难度比较高的题目了，再次说明，刷题一定要循序渐进，千万别想着直接就能解决难题，那只是对自己进行劝退处理。加油，平常心，一步步前进。
样例说明 取最后一列，和为10。 数据规模和约定 对于100%的数据，1< =n, m< =500，A中每个元素的绝对值不超过5000。
使用数据结构完成下列操作： 1.区间赋值为0 2.区间赋值为1 3.区间求和 4.区间取反 5.区间最大连续1数量
有一份航班预订表 bookings，表中第 条预订记录 意味着在从 到 （包含 和 ）的 每个航班 上预订了 个座位。
(y*query(tree,y)-(x-1)*query(tree,x-1))-(query(tree1,y)-query(tree1,x-1))
树状数组即二叉索引树，是使用数组模拟树形结构的一种数据结构，可用于计算前缀和和区间和(元素全为1时可用来计数)。采用数组而不是直接建树来解决问题是由于某些特定问题比如区间求和完全可以不建树就能解决，这样实现简单，复杂度低。这点上和Trie树有异曲同工之妙。
1080 线段树练习 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description 一行N个方格，开始每个格子里都有一个整数。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N<100000，,提问和修改的总数m<10000条。 输入描述 Input Description 输入文件第一行为一个整
线段树是算法竞赛中常用的数据结构（虽然考场中很少用，毕竟调起来麻烦，区间求和用树状树组还是更加方便代码也短）。
树状数组（Binary Index Tree, BIT）也是很多OIer心中最简洁优美的数据结构之一。最简单的树状数组支持两种操作，时间复杂度均为 ：
每次将区间的长度一分为二,区间存储的左右边界 [[start,end]/[left,right]]
实现功能——1：区间加法 2：区间乘法 3：区间覆盖值 4：区间求和 这是个四种常见线段树功能的集合版哦。。。么么哒（其实只要协调好三种tag的关系并不算太难——前提是想明白了线段树的工作模式） 代码长度几经修改后也大为缩水 还有！！！——通过BZOJ1798反复的尝试，我的出来一个重要结论——尽量减少pushup操作的不必要使用次数，对于程序提速有明显的效果！！！ 1 type vet=record 2 a0,a1:longint; 3 end; 4 var 5 i,j
显然从一个位置开始能影响到的位置是单调的，而且这些位置的每个改变量都是\((a_i + x) + \sum_{t=i}^{j-1} k_t\)
binary index tree 来自OI-wiki的图，我记得刘汝佳书里也有，不过那本书不在我手边
1，前缀和主要适用场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和。 这里就不写前缀和的代码了，就是用一个数组记录下原有数组的前缀和。比如，prefix[i]就代表着nums[0…i-1]所有元素的累加和，如果我们想求区间nums[i…j]的累加和，只要计算prefix[j + 1] – prefix[i]即可，而不需要遍历整个区间求和。（需要注意的是使用场景是频繁查询某个区间的累加和，而不需要对原始数组进行频繁修改） 2，查分数组的主要适用场景是**频繁对原始数组的某个区间的元素进行增减。**比如说，给定一个数组nums，要求给区间nums[2…6]全部加1，再给nums[3…9]全部减3，再给nums[0…4]全部加2,等等。当然可以使用for循环挨个处理，但是可以利用查分数组来达到O(1)复杂度就可以完成某个动作。diff[i]就是nums[i]和nums[i – 1]之差。比如： nums： 8 5 9 6 1 diff： 8 -3 4 -3 -5 首先可以通过这个数组来还原原来的数组，也可以利用O(1)复杂度完成给nums[i…j]全部加val的操作。只需两步即可，第一步：diff[i] += val， 这意味着nums[i…]的值全都加val，第二步：diff[j + 1] -= val(j + 1 < size)，这意味着nums[j + 1…]的值全都减val，因为第一步加了。
给出一个长为n的数列，以及n个操作，操作涉及区间加法，区间求和。 这题的询问变成了区间上的询问，不完整的块还是暴力；而要想快速统计完整块的答案，需要维护每个块的元素和，先要预处理一下。 考虑区间修改操作，不完整的块直接改，顺便更新块的元素和；完整的块类似之前标记的做法，直接根据块的元素和所加的值计算元素和的增量。 更改后的区间加法 1 void interval_add(LL ll,LL rr,LL v) 2 { 3 for(LL i=ll;i<=min(where[ll]*m,rr);i++
在以上5个求和函数中，如果按 功能 + 计算速度 ＋ 易用性 3个角度综合评比，Sumifs是当之无愧的No.1。今天兰色就全面讲解这个最常用的多条件求和函数用法。
$= sum_{i = 1}^x (x+1)d_i - \sum_{i = 1}^x id_i$
给定一个包含非负数的数组和一个目标整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
差分数组是一种高效的算法技巧，它在处理数组区间操作时特别有用。当你需要频繁地对数组的某个区间进行元素的增减操作时，使用差分数组可以显著提高效率。这种方法的核心思想是利用差分来避免对整个区间进行逐个元素的修改。
bzoj 1858. [Scoi2010]序列操作 题解 Description 题目链接：BZOJ1858 [Scoi2010]序列操作 给你长度为n的01串，现有m个操作。 区间赋值为0 区间赋值为1 区间反转（所有0变为1，所有1变为0） 区间求和 求区间最多有连续的几个1 对于100\%的数据，1\le n,m \le 100000。 Solution 珂朵莉树，如果您还不了解珂朵莉树，可以参见我的这篇博客。 由于Luogu上的数据已加强，故只能过3个点，但bzoj可过。 Code #in
实现功能——1：区间加法；2：区间求和 最基础最经典的线段树模板。由于这里面操作无顺序之分，所以不需要向下pushup，直接累积即可 1 var 2 i,j,k,l,m,n,a1,a2,a3,a4:longint; 3 a,b:array[0..100000] of longint; 4 function max(x,y:longint):longint;inline; 5 begin 6 if x>y then max:=x else
如果我们要求一个数组内任意区间的和，最朴素的算法是每次对区间所有元素进行求和运算，时间复杂度为O(n)。也可以考虑用前缀和的方式去实现，求和运算的时间复杂度为O(1)，但这样一来，如果对数组的某一项进行修改，则要同步维护前缀和数组，这会导致更新操作的时间复杂度由原来的O(1)提升为O(n)。如果数据量非常巨大，这样的时间复杂度仍然是不被接受的。
实现功能——1：区间覆盖值；2：区间求和 相比直接的区间加，这个要注重顺序，因为操作有顺序之分。所以这里面的tag应该有个pushup操作（本程序中的ext） 1 var 2 i,j,k,l,m,n,a1,a2,a3,a4:longint; 3 a,b,d:array[0..100000] of longint; 4 function max(x,y:longint):longint;inline; 5 begin 6 if x>y th
实现功能——1：区间开根；2：区间求和（此模板以BZOJ3038为例） 作为一个非常规的线段树操作，其tag也比较特殊呵呵哒 1 var 2 i,j,k,l,m,n:longint; 3 a,b:array[0..500000] of int64; 4 function max(x,y:longint):longint;inline; 5 begin 6 if x>y then max:=x else max:=y; 7
的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
小T 是一名质量监督员，最近负责检验一批矿产的质量。这批矿产共有 n 个矿石，从 1 到 n 逐一编号，每个矿石都有自己的重量
前言 树链剖分是什么？ 树链剖分，说白了就是一种让你代码不得不强行增加1k的数据结构-dms 个人理解：+1:joy: 有什么用？ 证明出题人非常毒瘤 可以非常友(bao)好(li)的解决一些树上问题:grimacing: （友情提示：学树链剖分之前请先掌握线段树） 核心思想 树链剖分的思想比较神奇 它的思想是：把一棵树拆成若干个不相交的链，然后用一些数据结构去维护这些链 那么问题来了 如何把树拆成链？ 首先明确一些定义 重儿子：该节点的子树中,节点个数最多的子树的根节点(也就是和该节点相连的点)
1082 线段树练习 3 时间限制: 3 s 空间限制: 128000 KB 题目等级 : 大师 Master 题目描述 Description 给你N个数，有两种操作： 1：给区间[a,b]的所有数增加X 2：询问区间[a,b]的数的和。 输入描述 Input Description 第一行一个正整数n，接下来n行n个整数， 再接下来一个正整数Q，每行表示操作的个数， 如果第一个数是1，后接
暴力超时，这道题可以用线段树做，因为更新的是单个节点，我们也可以用数组数组来做，我将两种方法的代码都给出
现在有一个数组a，我们需要求很多次数组中不同区间的和，而且多次对a中随意一项进行更改。 比如说a = {0, 1, 5, 3, 2, 4}
题目描述 如题，已知一个数列，你需要进行下面两种操作： 1.将某区间每一个数加上x 2.求出某区间每一个数的和 输入输出格式 输入格式： 第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。 第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。 接下来M行每行包含3或4个整数，表示一个操作，具体如下： 操作1： 格式：1 x y k 含义：将区间[x,y]内每个数加上k 操作2： 格式：2 x y 含义：输出区间[x,y]内每个数的和 输出格式： 输出包含
数据结构是计算机科学中的一个重要概念，它描述了数据之间的组织方式和关系，以及对这些数据的访问和操作。常见的数据结构有：数组、链表、栈、队列、哈希表、树、堆和图。
敌兵布阵 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 64577 Accepted Submission(s): 27214 Problem Description C国的死对头A国这段时间正在进行军事演习，所以C国间谍头子Derek和他手下Tidy又开始忙乎了。A国在海岸线沿直线布置了N个工兵营地,Derek和Tidy的任务就是
是用来存放给定区间（segment, or interval）内对应信息的一种数据结构。与树状数组（binary indexed tree）相似，线段树也用来处理数组相应的区间查询（range query）和元素更新（update）操作。与树状数组不同的是，线段树不止可以适用于区间求和的查询，也可以进行区间最大值，区间最小值（Range Minimum/Maximum Query problem）或者区间异或值的查询。
内存限制：256 MiB时间限制：500 ms标准输入输出 题目类型：传统评测方式：文本比较 上传者： hzwer 提交提交记录统计讨论测试数据 题目描述 给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及区间加法，区间求和。 输入格式 第一行输入一个数字 nnn。 第二行输入 nnn 个数字，第 i 个数字为 ，以空格隔开。 接下来输入 nnn 行询问，每行输入四个数字 opt\mathrm{opt}opt、lll、rrr、ccc，以空格隔开。 若 opt=0\mathrm{opt} = 0
📷 📷 1.动态规划 这题是让求最大的连续子序和，如果不是连续的非常简单，只需要把所有的正数相加即可。但这里说的是连续的，中间可能掺杂负数，如果求出一个最大子序和在加上负数肯定要比原来小了。解这题最简单的一种方式就是使用动态规划。 我们先来了解一下动态规划的几个步骤： 1，确定状态 2，找到转移公式 3，确定初始条件以及边界条件 4，计算结果。 最后一个不用看，只看前3个就行，因为前3个一旦确定，最后一个结果也就出来了。我们试着找一下 1，定义dp[i]表示数组中前i+1（注意这里的i是从0开始的）个元
我们在刷题时经常会遇到和区间有关的题目，最典型的是区间求和，给你一个数组，求出从 到 这一段子区间的所有元素的和。比如leetcode 307.区域检索-数组可修改
内存限制：256 MiB时间限制：500 ms标准输入输出 题目类型：传统评测方式：文本比较 上传者： hzwer 提交提交记录统计讨论 1 测试数据 题目描述 给出一个长为 nnn 的数列，以及 nnn 个操作，操作涉及区间开方，区间求和。 输入格式 第一行输入一个数字 nnn。 第二行输入 nnn 个数字，第 i 个数字为 aia_iai，以空格隔开。 接下来输入 nnn 行询问，每行输入四个数字 opt\mathrm{opt}opt、lll、rrr、ccc，以空格隔开。 若 opt=0\m
大家好，我是算法老司机 labuladong，本文给大家介绍一个小而美的算法技巧：差分数组。
线段树是一棵二叉树，他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数，并按照如下的方式赋值:
这是 LeetCode 上的「2213. 由单个字符重复的最长子字符串」，难度为「困难」。
上图 from 熊掌搜索 类似数据结构：树状数组 1. 概念 线段树是一种二叉树，是用来表示一个区间的树： 常常用来查询区间的：和、最小值、最大值 树结点中存放不是普通二叉树的值，其结点结构如下 cl
如果要求区间[a,b]的和，那第一想法就是直接遍历区间[a,b]，把所有的加起来就行了。但这样效率太低，总共进行b-a+1次操作，O(n)复杂度。
Fail指针的基本性质：某只结点的Fail指针，指向它所代表的字符串的最长的后缀的结点。
有n个节点以1为根节点的树，给你树的边关系u-v，一开始每个节点都有一个苹果，接下来有两种操作，C x改变节点x的苹果状态，Q x查询x为根的树的所有苹果个数。
给定 n 个数的序列 {a_i}，有 m 组询问，每次询问给定区间 [l,r]，问有多少个子区间 [i,j] 满足 a_i,\dots,a_j 中不同的整数的数目是奇数。
线段树是一个复杂的数据结构，比较难理解，也比较难解释清楚。在我将这个数据结构反复学习了五遍的时候，我终于有了信心写出这篇介绍线段树的文章。希望大家能够掌握这种数据结构。
PS：这是一年前发布的 论那些小而美的算法技巧：差分数组/前缀和，我优化并添加了很多内容，重新发一遍。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储
