首页 > 其他分享 >前缀和与差分

前缀和与差分

时间:2023-07-03 16:01:40浏览次数:40  
标签:... 前缀 差分 查询 数组 习题

前缀和

令 \(s[i] = a[1] + a[2] + ... + a[i]\) ,此时的 \(s\) 数组就为 \(a\) 数组的前缀和。

实现:
每个 \(s[i]\) 都可由 \(s[i - 1] + a[i]\) 转换来,顺序处理即可。

代码:

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

应用:
常用于求区间和。即 \(a[l] + a[l + 1] ... + a[r] = s[r] - s[l - 1]\) 。

习题:
LOT-A Journey to Mars

差分

令 \(b[i] = a[i] - a[i - 1]\) ,此时的 \(b\) 数组就为 \(a\) 数组的差分数组。因为有 \(b[1] + b[2] + ... + b[i] = a[i]\) ,即 \(a\) 数组为 \(b\) 数组的前缀和。

代码:

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

应用:
用于进行快速的区间加。即若将 \(a\) 数组的 \(l - r\) 项同时加上 \(k\) ,等同于 \(b[l] += k\) 且 \(b[r + 1] -= k\) 。最后将 \(b\) 数组进行前缀和得出的即为要求的 \(a\) 数组。

习题:
语文成绩

前缀和于差分

在区间加问题中,前缀和做法为修改 \(O(n)\) ,查询 \(O(1)\) ;而差分做法为修改 \(O(1)\) ,查询 \(O(n)\) 。
可按题目要求在两种做法中进行选择。
折中算法:树状数组(修改 \(O(logn)\) ,查询 \(O(logn)\))

标签:...,前缀,差分,查询,数组,习题
From: https://www.cnblogs.com/biuld/p/17523121.html

相关文章

  • 【差分 Trick】CF626F Group Projects
    模拟赛垫底哥来补题了。先排序,考虑到原来的弱智状态难以描述,我们可以这样写:\(f_{i,j,k}\)表示前\(i\)个,\(j\)段未闭合,目前的不协调值为\(k\)。然后喜提\(n^2\suma_i\)的时间复杂的。然后就是经典tricktime,这个可以看作很多线段。然后\(a_r-a_l=\suma_{i+......
  • 医学案例|单因素方差分析
    一、案例介绍为研究郁金对低张性缺氧小鼠存活时间的影响,将36只小鼠随机生成A、B以及C三组,,每组12个,雌雄各半,分别以10g/kg、20g/kg、40g/kg三种不同剂量的郁金灌胃,各组小鼠均同时置于放有钠石灰的250ml密闭广口瓶中,观察并记录小鼠存活时间。想要研究不同剂量的郁金下的小鼠的存......
  • 前缀长度转成子网掩码
    原文地址:https://www.cnblogs.com/liqinglucky/p/ipv6_mask.html将前缀长度转成子网掩码#include<stdio.h>#include<sys/types.h>#include<sys/socket.h>#include<arpa/inet.h>#include<string.h>#include<stdlib.h>intmask_fun(intm......
  • CF1843E 二分+前缀和
    题意:给定一个长度为n且均为0的数组,q次单点修改(从0改为1),以及m个基于该数组的区间。规定好区间为:区间内1的个数严格大于0的个数。上述m个区间若存在一个好区间则为合法,问按顺序进行q次单点修改过程中最早出现合法的单次修改编号,若无则输出-1。马后炮思考:对于m个区间,其实际关系......
  • 基于STM32单片机的差分升级和增量升级算法源码,这些源码可以在不同平台上进行移植
    基于STM32单片机的差分升级和增量升级算法源码,这些源码可以在不同平台上进行移植。此外,IAP升级和OTA升级技术,这些技术在物联网和车联网领域中得到广泛应用。原创文章,转载请说明出处,资料来源:http://imgcs.cn/5c/653978935134.html提取的知识点和领域范围:1.单片机(STM32):单片机是一......
  • leetcode-前缀和数组&差分数组
    前缀和数组:前缀和技巧适用于快速、频繁地计算一个索引区间内的元素之和。(仅仅适用于原数组不变的情况,如果原数组经常修改,则需要考虑差分数组。)模版如下:classPrefixSum{//前缀和数组privateint[]preSum;/*输入一个数组,构造前缀和*/publicPrefixSu......
  • Python字符串前缀u、r、b、f含义
    Python字符串前缀u、r、b、f含义1、字符串前加u例子:u"字符串中有中文"含义:前缀u表示该字符串是unicode编码,Python2中用,用在含有中文字符的字符串前,防止因为编码问题,导致中文出现乱码。另外一般要在文件开关标明编码方式采用utf8。Python3中,所有字符串默认都是unicode字符串......
  • 强化学习从基础到进阶-常见问题和面试必知必答[3]:表格型方法:Sarsa、Qlearning;蒙特卡洛
    强化学习从基础到进阶-常见问题和面试必知必答[3]:表格型方法:Sarsa、Qlearning;蒙特卡洛策略、时序差分等以及Qlearning项目实战1.核心词汇概率函数和奖励函数:概率函数定量地表达状态转移的概率,其可以表现环境的随机性。但是实际上,我们经常处于一个未知的环境中,即概率函数和奖励......
  • 强化学习从基础到进阶-案例与实践[3]:表格型方法:Sarsa、Qlearning;蒙特卡洛策略、时序差
    强化学习从基础到进阶-案例与实践[3]:表格型方法:Sarsa、Qlearning;蒙特卡洛策略、时序差分等以及Qlearning项目实战策略最简单的表示是查找表(look-uptable),即表格型策略(tabularpolicy)。使用查找表的强化学习方法称为表格型方法(tabularmethod),如蒙特卡洛、Q学习和Sarsa。本章通过最......
  • 强化学习从基础到进阶-常见问题和面试必知必答[3]:表格型方法:Sarsa、Qlearning;蒙特卡洛
    强化学习从基础到进阶-常见问题和面试必知必答[3]:表格型方法:Sarsa、Qlearning;蒙特卡洛策略、时序差分等以及Qlearning项目实战1.核心词汇概率函数和奖励函数:概率函数定量地表达状态转移的概率,其可以表现环境的随机性。但是实际上,我们经常处于一个未知的环境中,即概率函数和奖励......