实用数据结构小结（树状数组、st表、bitset）

前言 一、树状数组 1.功能介绍

树状数组可以认为是线段树的青春版

树状数组它有着丰富的功能，虽然不及线段树，但它代码简洁，思维清晰，速度也更快

它和st表有点相似，但功能相对更丰富些，树状数组仅靠一维数组便维护了整个区间具体为： c [ k ] = ∑ i = k − l o w b i t ( k ) + 1 k a [ i ] c[k]=\sum_{i=k-lowbit(k)+1}^{k}a[i] c[k]=i=k−lowbit(k)+1∑k​a[i] l o w b i t ( x ) = x & ( − x ) lowbit(x)=x\&(-x) lowbit(x)=x&(−x)

它支持单点修改、区间修改（需要进行前缀变换）、单点查询、区间查询功能

树状数组的区间查询建立在前缀和的基础上，因此想让它求区间最值还得需要一定的变换，比较复杂，不推荐

int query(int x, int y) {
  int ans = 0;  // (log n) ^ 2
  while (y >= x) {
    ans = max(a[y], ans);
    y--;
    for (; y - lowbit(y) >= x; y -= lowbit(y)) ans = max(c[y], ans);
  }
  return ans;
}

所以它的应用场景一般就集中在数据查询，和逆序对上

此外，值得一提的是它可以与莫队结合求区间逆序对 贴一张图方便理解，图源 https://blog.csdn.net/bestsort/article/details/80796531

2.例题 p3374

单点修改、区间求和 题目链接 洛谷p3374 代码如下：

#include 
using namespace std;
const int maxn = 5e5 + 5;
int n, m;
int a[maxn], c[maxn];
int lowbit(int x) { return x & (-x); }  // x 最后一位是 1 的位数
void update(int x, int val) {           // c[k] = a[k-lowbit(i)+1] + ... + a[k]
  for (int i = x; i