2026年区域和检索试题及答案

2026年区域和检索试题及答案某城市气象站记录了2026年3月1日至3月n日的日平均温度，存储在数组temp中（下标从1开始）。现需要处理m次查询，每次查询给出两个整数l和r（1≤l≤r≤n），要求计算第l天到第r天的温度总和。输入格式：第一行包含两个整数n和m（1≤n≤1e5，1≤m≤1e5）；第二行包含n个整数，表示temp[1..n]；接下来m行，每行两个整数l和r。输出格式：共m行，每行一个整数，表示对应查询的温度总和。答案：由于是静态数组（无更新操作），多次区间查询最有效的方法是使用前缀和数组。定义前缀和数组preSum，其中preSum[i]表示temp[1..i]的和，则区间[l,r]的和为preSum[r]preSum[l-1]。具体步骤如下：1.读取n和m，读取temp数组。2.构建preSum数组：preSum[0]=0，preSum[i]=preSum[i-1]+temp[i]（i从1到n）。3.对于每个查询l和r，输出preSum[r]preSum[l-1]。时间复杂度：预处理O(n)，每次查询O(1)，总复杂度O(n+m)，适用于1e5级别的输入规模。某图书馆记录了2026年上半年每日的借书数量（还书视为负的借书量），存储在数组book中（下标从1开始）。系统需要支持两种操作：操作1为单点更新，将第x天的借书量增加v（v可正可负）；操作2为区间查询，计算第l天到第r天的总借书量。输入格式：第一行包含两个整数n和q（1≤n≤1e5，1≤q≤1e5）；第二行包含n个整数，表示book[1..n]；接下来q行，每行三个整数，第一个数为操作类型（1或2），若为1则后接x和v，若为2则后接l和r。输出格式：对于每个操作2，输出一个整数，表示对应区间的总借书量。答案：需要支持单点更新和区间查询，树状数组（FenwickTree）是高效选择。树状数组通过维护前缀和的增量，实现O(logn)时间的单点更新和区间查询。区间[l,r]的和等于前缀和到r减去前缀和到l-1。具体实现：1.初始化树状数组，大小为n，初始值通过逐个位置更新设置。2.操作1（单点更新）：调用update(x,v)，将位置x的值增加v。3.操作2（区间查询）：计算query(r)query(l-1)，其中query(x)返回前缀和到x。树状数组的update操作通过lowbit运算向上更新相关节点，query操作通过lowbit运算累加前缀和。时间复杂度：每次操作O(logn)，总复杂度O(n+qlogn)，适用于1e5级别的输入。某农场有一块n×m的矩形农田，划分为n行m列的网格，每个网格记录了2026年的预计产量（单位：公斤），存储在二维数组crop中（下标从1开始）。系统需要支持两种操作：操作1为单点更新，将第i行第j列的产量修改为v；操作2为区域查询，计算从第x1行y1列到第x2行y2列（x1≤x2，y1≤y2）的矩形区域内的总产量。输入格式：第一行包含三个整数n、m、q（1≤n,m≤2e3，1≤q≤1e4）；接下来n行，每行m个整数，表示crop[1..n][1..m]；接下来q行，每行包含若干整数：若为操作1，输入1ijv；若为操作2，输入2x1y1x2y2。输出格式：对于每个操作2，输出一个整数，表示对应区域的总产量。答案：二维区域查询和单点更新可使用二维树状数组。二维树状数组通过维护二维前缀和的增量，支持O(lognlogm)时间的单点更新和区域查询。区域[x1,y1,x2,y2]的和可通过二维前缀和公式计算：sum=query(x2,y2)query(x1-1,y2)query(x2,y1-1)+query(x1-1,y1-1)，其中query(x,y)表示(1,1)到(x,y)的矩形和。具体实现：1.初始化二维树状数组，逐元素更新初始值。2.操作1（单点更新）：计算新值与旧值的差值delta，调用update(i,j,delta)，并更新原数组。3.操作2（区域查询）：利用二维前缀和公式计算结果。时间复杂度：每次更新和查询O(lognlogm)，n和m为2e3时，log2(2e3)≈11，总运算量可接受。某在线游戏中，玩家按等级划分为1到n级（n≤1e5），每个等级有若干玩家，记录每个等级的总经验值存储在数组exp中（下标从1开始）。运营活动需要支持两种操作：操作1为区间加法，对等级在[l,r]范围内的所有等级，每个等级的总经验值增加v；操作2为区间查询，计算等级在[l,r]范围内的总经验值之和。输入格式：第一行包含两个整数n和q（1≤n≤1e5，1≤q≤1e5）；第二行包含n个整数，表示exp[1..n]；接下来q行，每行三个整数，第一个数为操作类型（1或2），若为1则后接l、r、v；若为2则后接l、r。输出格式：对于每个操作2，输出一个整数，表示对应区间的总经验值之和。答案：区间加法和区间查询需使用线段树配合懒标记。线段树每个节点存储区间和sum和待下传的加法标记add。区间加法时，若当前节点区间完全包含在目标区间内，更新sum和add；否则下传标记后递归处理子节点。区间查询时，若当前节点区间完全包含在目标区间内返回sum，否则下传标记后递归查询子节点。具体实现：1.构建线段树，叶节点存储exp数组值，内部节点存储子节点和。2.操作1（区间加法）：调用rangeAdd(l,r,v)，更新对应区间的sum和add。3.操作2（区间查询）：调用rangeQuery(l,r)，返回区间和。时间复杂度：线段树构建O(n)，每次操作O(logn)，总复杂度O(n+qlogn)，适用于1e5级别的输入。某电商平台统计2026年某类商品的日销售额，存储在数组sales中（下标从1开始）。系统需要支持三种操作：操作1为区间加法，对第l到r天的销售额每个增加v；操作2为区间乘法，对第l到r天的销售额每个乘以k（k为浮点数，保留两位小数）；操作3为区间查询，计算第l到r天的总销售额之和（结果保留两位小数）。输入格式：第一行包含两个整数n和q（1≤n≤1e5，1≤q≤1e5）；第二行包含n个浮点数，表示sales[1..n]（保留两位小数）；接下来q行，每行包含若干整数和浮点数：若为操作1，输入1lrv；若为操作2，输入2lrk；若为操作3，输入3lr。输出格式：对于每个操作3，输出一个浮点数，保留两位小数，表示对应区间的总销售额之和。答案：同时支持区间加法、乘法和求和，需使用线段树维护乘法标记（mul）和加法标记（add），且乘法优先于加法。每个节点sum表示区间和，mul初始为1.0，add初始为0.0。区间乘法时，sum=k，mul=k，add=k；区间加法时，sum+=vlen（len为区间长度），add+=v。下传标记时先处理乘法，再处理加法。具体实现：同时支持区间加法、乘法和求和，需使用线段树维护乘法标记（mul）和加法标记（add），且乘法优先于加法。每个节点sum表示区间和，mul初始为1.0，add初始为0.0。区间乘法时，sum=k，mul=k，add=k；区间加法时，sum+=vlen（len为区间长度），add+=v。下传标记时先处理乘法，再处理加法。具体实现：1.构建线段树，叶节点存储sales数组值，内部节点存储子节点和。2.操作1（区间加法）：调用rangeA