网课-数据结构学习笔记2

树状数组

局限性：若区间信息不可减（即无法由两个前缀信息推出），树状数组就显得力不从心了。

• P6225 [eJOI2019] 异或橙子

  Trick：异或具有交换律、结合律，可拆开考虑每个位置的贡献。

• P3372 【模板】线段树 1

  算法：区修区查树状数组

  核心思想是将式子拆开，维护 \(\sum c[i]\) 与 \(\sum c[i]*i\)。

  Trick：拆分式子，独立维护项。

• P6619 [省选联考 2020 A/B 卷] 冰火战士

  算法：树上数组上倍增

  Trick：关于值域的问题就考虑维护关于值域的桶。