基础数据结构(前缀和/差分/树状数组/线段树)学习笔记

前缀和与差分

多维前缀和

多维前缀和可以通过一维一维处理的方式,将复杂度控制在可控范围。
例如二维前缀和求法:
1. $sum_{i,j}=a_{i,j}$
2. $sum_{i,j}+=sum_{i-1,j}$
3. $sum_{i,j}+=sum_{i,j-1}$

例题:NC225630 智乃酱的子集与超集

数列上加多项式

给一个数列的一部分连续的数分别加上 $f(1),f(2),\dots,f(n),\dots$
key:任何一个最高次数为 $n$ 的多项式连续数列可以通过差分 $n+1$ 次表示。
因此,对于区间 $(l,r)$,我们先差分出一个从 $l$ 开始的 $f(1)$ 开始的数列,再差分出一个从 $r+1$ 开始的 $-f(r-l+2)$ 开始的数列抵消影响。
例题:NC225628 智乃酱的静态数组维护问题多项式

树状数组与线段树

离线后树状数组

一些统计种类的问题可以通过这个方法来解决。
例如 [HEOI2012]采花

LazyTag

懒标记是线段树的核心之一。考虑需要维护的数值在懒标记下的运算很关键。
给出例题:
线段树
智乃酱的cube

带修改的 DP(DDP)

通过线段树可以完成一些能通过矩阵优化的 DP 的待修改版本。
智乃酱的双塔问题·极(带修改的DP,DDP)
智乃酱的双塔问题·改

势能线段树(带暴力成分的线段树)

有些数据具有单调性,就像势能不断下降至 0 势能点,观察并维护之可以让一些线段树结构看似有暴力修改,实则复杂度合法。
势能线段树模板题二
弩蚊怒夏

李超线段树

李超线段树是用来维护平面上的若干点的,用于快速找出在某一个 x 坐标,那一条的 y 值最大或最小。这在动态规划优化中也有作用。
模板:智乃的直线

本文作者:water_tomato
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇