Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"洛谷-P2367\":[\"语文成绩\",33944,null],\"洛谷-P3865\":[\"ST 表\",74646,\"模板\"],\"洛谷-P1115\":[\"最大子段和\",111664,null],\"洛谷-P2104\":[\"二进制\",2293,null],\"洛谷-P1226\":[\"快速幂\",107134,\"模板\"],\"洛谷-P1517\":[\"高精求小数幂\",1323,null],\"洛谷-B3612\":[\"求区间和\",12735,\"深进1.例1\"],\"洛谷-B3645\":[\"数列前缀和 2\",895,null],\"洛谷-B3694\":[\"数列离散化\",2300,null],\"洛谷-P1496\":[\"火烧赤壁\",16561,null],\"洛谷-P4122\":[\"Blocked Billboard B\",1639,\"USACO17DEC\"],\"洛谷-P4552\":[\"IncDec Sequence\",11708,\"Poetize6\"],\"洛谷-P9532\":[\"前缀和\",1676,\"YsOI2023\"]}","joined":false,"groups":{}},"managingGroups":{},"author":"Exile_code","updateTime":1706702194000,"title":"基础算法入门(预处理)","dislikeCnt":0,"content":"# 基础算法入门(预处理)\n\n## 前言\n\n预处理是算法中的一种优化技术,通过在实际算法执行之前对输入数据进行某些预先计算,可以提高算法的效率。预处理的目标是通过提前计算一些信息减少算法运行时的重复计算或者缩小问题的的范围来简化问题的解决方案。\n\n预处理作用之一是将一些原本需要在算法主循环中执行的操作提前处理,从而减少算法的时间复杂度。例如在循环中需要重复计算某个值,可以先将这个值算出,避免重复。本质是通过空间换时间的方式,去存储需要多次计算的信息,来避免在循环中多次重复计算。\n\n预处理有时可以将原始问题转化为更容易处理的形式。通过预处理,可以将问题的输入或约束转化为一种更方便的表示形式,使得算法的设计更为简单。\n\n## 前缀和与差分\n\n### 简介\n\n前缀和是数组中从开头到某个位置的所有元素的和。通过预计算前缀和,我们可以在常数时间内获取数组中任意区间的和。用于高效计算数组中某个区间的和,例如解决子数组和的问题。\n\n差分通过将相邻元素之间的差值存储在新数组中,可以实现在某个区间内的元素增减操作。用于高效更新数组中某一范围内的元素值。\n\n### 学习链接\n\n[【C++算法基础】#9前缀和与差分 | 轻松学算法 | 图解ACM竞赛算法_哔哩哔哩](https://www.bilibili.com/video/BV1NX4y147G5/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n### 练习\n\n[problem:洛谷-B3612],[problem:洛谷-P9532],[problem:洛谷-P1115],[problem:洛谷-P2367],[problem:洛谷-P4552],[problem:洛谷-CF1722E],[problem:洛谷-B3645]\n\n## 倍增\n\n### 简介\n\n倍增用于高效计算指数幂,通过二进制分解指数来减少乘法的次数。在一些数学问题中,例如快速幂求解。\n\n### 学习链接\n\n[G01 快速幂_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1pe411u77y/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n[算法竞赛——倍增思想及其应用_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1vQ4y1r7ms/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n[D09 倍增算法 P3379【模板】最近公共祖先(LCA)_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1vg41197Xh/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n### 练习\n\n[problem:洛谷-P1226],[problem:洛谷-P3865],[problem:洛谷-P1517],[problem:洛谷-CF1665B],[problem:洛谷-SP14932]\n\n## 离散化\n\n### 简介\n\n将一组具有一定范围的数映射为连续的整数,常用于处理离散值。在一些问题中,通过离散化可以将问题转化为对连续整数的处理,方便使用一些数据结构。\n\n### 学习链接\n\n[【基础算法】离散化_哔哩哔哩_bilibili](https://www.bilibili.com/video/BV1E3411W7G5/?vd_source\u003d204bd6a950e12dc2a5fd501f88a334d9)\n\n### 练习\n\n[problem:洛谷-B3694],[problem:洛谷-P4122],[problem:洛谷-P1496],[problem:洛谷-CF1676F],[problem:洛谷-P2104]","threadId":181141,"likeCnt":1,"createTime":1706699020000,"isWorkbook":true,"viewCnt":380,"openness":2,"fav":false,"id":4535,"trustable":false}