珂朵莉树 学习笔记

什么是珂朵莉树?

珂朵莉树,又称$ODT(Old Driver Tree)$,是一个基于$std::set$的暴力、玄学数据结构。

什么时候使用珂朵莉树?

如果有一题涉及到区间赋值(即把区间内所有的数全部赋值成同一个量)的操作,且数据随机,就可以考虑使用珂朵莉树。

下面以一道例题CF896来详解珂朵莉树。

Description

给你$n$个数,要求进行$m$次操作。

  1. 区间加
  2. 区间赋值
  3. 求区间第$k$小
  4. 求区间每个数的幂的和

保证数据随机

Solution

珂朵莉树的板子

首先定义珂朵莉树

不知道$mutable$?点击此了解详情

珂朵莉树操作

核心操作——split

如果要修改某一个区间,那么肯定要把区间拆出来。

推平操作——assign

珂朵莉树是靠推平操作来减小复杂度的。由于数据随机,就有约$\frac{1}{4}$的操作是推平操作,使得$set$大小飞速下降,从而保证了复杂度。

那么为啥要先$split(r+1)$呢?因为如果先$split(l)$根据$split$中的$erase$操作,迭代器$it1$可能会失效。(因为$it1$所属的节点可能被删除了)

区间加
求区间第k小
求区间每个数的幂的和

Code

评论

发送评论 编辑评论


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