BIT 和线段树练习题
题单介绍
[更多题目预览](https://www.cnblogs.com/ICELX/p/19012911)
### 简介
这个题单统计了思维含量中低等 BIT 和线段树的题，的~~其实并不都是水题~~。
难度按升序排序，根据数据范围，这个题单的题线段树应该都可以做。
适合刚学完或复习 BIT 和线段树的选手提高思维能力或~~水题~~。
------------
## 考点分类
### BIT 板子：
#### 思路：
修改板子。
#### 题目：
P3374 【模板】树状数组 1
P3368 【模板】树状数组 2
UVA12086 Potentiometers
P4939 Agent2
P2068 统计和
P5057 [CQOI2006] 简单题
### 权值 BIT：
#### 思路：
在值域上建立 BIT 或线段树，配合离散化解决问题。
#### 题目：
P1168 中位数
P1908 逆序对
UVA10810 Ultra-QuickSort
B3874 [GESP202309 六级] 小杨的握手问题
P1966 [NOIP 2013 提高组] 火柴排队
### 二阶/二次 BIT：
#### 思路：
由二阶/二次前缀和拓展至二阶/二次 BIT，维护两个 BIT，一个记录一阶/一次前缀和，另一个记录二阶/二次前缀和，根据题目性质解决问题。
对于线段树的思路，在前缀数组上建立线段树，维护前缀和的更新与查询。
#### 题目：
P2345 [USACO04OPEN] MooFest G
P5094 [USACO04OPEN] MooFest G 加强版
P4868 Preprefix sum
P1438 无聊的数列
### 思维题
#### 思路：
根据题目，分析题目性质，找到突破口，合理运用 BIT 或线段树解决问题。
#### 题目：
P6225 [eJOI 2019] 异或橙子
P5200 [USACO19JAN] Sleepy Cow Sorting G
P2184 贪婪大陆
### 线段树板子
#### 思路：
修改板子，注意标记上的细节问题。
#### 题目
P3372 【模板】线段树 1
P3373 【模板】线段树 2
P2357 守墓人
P3130 [USACO15DEC] Counting Haybale P
P1531 I Hate It
P2023 [AHOI2009] 维护序列
P1253 扶苏的问题
### 简单变式
#### 思路：
在模板的基础上融入一定的思维，解决问题。
#### 题目：
P1198 [JSOI2008] 最大数
P12539 [XJTUPC 2025] 结束乐队
P4588 [TJOI2018] 数学计算
### 三倍经验
#### 思路：
用异或维护懒标记即可。
#### 题目：
P2574 XOR的艺术
P2846 [USACO08NOV] Light Switching G
P3870 [TJOI2009] 开关
### 权值线段树
#### 思路：
~~选了两道主席树裸题，权值 BIT 也可以做~~。
在值域上建立 BIT 或线段树，配合离散化解决问题。
#### 题目：
P10589 楼兰图腾
P1637 三元上升子序列
### 区间合并
#### 思路：
这些在合并区间上具有一定的技巧，特意准备了两倍经验和三倍经验各一组。
#### 题目：
P6492 [COCI 2010/2011 #6] STEP
UVA11235 Frequent values
SP1684 FREQUENT - Frequent values
SP1043 GSS1 - Can you answer these queries I
P4513 小白逛公园
SP1716 GSS3 - Can you answer these queries III
P2894 [USACO08FEB] Hotel G
UVA1400 "Ray, Pass me the dishes!"
### 思维题
#### 思路：
根据题目，分析题目性质，找到突破口，合理运用线段树解决问题，注意标记的设计和区间的合并。准备了一组双倍经验。
#### 题目：
P4085 [USACO17DEC] Haybale Feast G
P1558 色板游戏
P8818 [CSP-S 2022] 策略游戏
P4145 上帝造题的七分钟 2 / 花神游历各国
SP2713 GSS4 - Can you answer these queries IV
P1471 方差
P2221 [HAOI2012] 高速公路
P2824 [HEOI2016/TJOI2016] 排序
P9989 [Ynoi Easy Round 2023] TEST_69