上述三种数据结构都是对区间信息的维护与查询，把他们放在一起更加明了。二叉索引树BIT主要用于动态连续和查询问题，比如用于数据的动态更新和区间求和。这些功能线段树也具备，并且他们的查询和更新操作都是O(logn），但是线段树是通过不断地比较来缩小范围，比较操作非常花时间，使得性能低于二叉索引树。Sparse-Table的功能是处理静态RMQ问题，这些线段树不仅能实现，还能进行动态RMQ操作。但是Sparse-Table只需要建树O(nlogn)，查询操作只需要O（1），大大的提高了效率。每个数据结构都有各自的优点，所以不能因为线段树的全能而忽略了这些性能更优的结构。下面会简单讲解这三种数据结构，算法蓝皮书也有介绍（P194--P208）；
二叉索引树BIT；
给定一个n个元素的数组A1，A2，.....，An，设计一个数据结构，能完成
Add（x,d）操作：让Ax增加d。
Query（L,R）：计算A（l）+A（l+1）+....A（R）；
对于正整数x，我们定义lowbit（x）为x的二进制表达式中最右边的1所对应的值。所以lowbit（x）=x&-x；（-x是x的补码，所以x&-x为二进制表达式中最右边的1所对应的值）。
对于节点i，如果它是左子节点，那么他的父节点编号是i+lowbit（i）；如果他是右子节点，那么他们的父节点编号是i-lowbit（i）。构造一个辅助数组c，其中
Ci=A（i-lowbit(i)+1)+A(i-lowbit(i)+2)+....+A(i)
有了数组c之后，如何计算前缀和si呢？顺着节点i往左走，边走边往上爬，把沿途经过的Ci累加起来就行了，代码如下：
int sum(int x)
{int s=0;while(x>0){s=s+c[x];x=x-lowbit(x);}return s;
}而如果修改了一个Ai，如何更新C数组元素呢？从Ci开始往右走，边走边往上爬，代码如下：
void add(int x, int d )
{while(x<=n) {c[x]=c[x]+d;x=x+lowbit(x);}
}下面粘一个完整模板（这只是个点更新的，区间更新我不会哈哈哈）
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>using namespace std;//求lowbit
int lowbit(int x)
{return x&(-x);
}int c[1001];//计算从1到x的数组元素的和c
int sum(int x)
{int s=0;while(x>0){s=s+c[x];x=x-lowbit(x);}return s;
}//将A(x)的值增加d，也可以减掉某个值
void add(int x, int d )
{while(x<=n){c[x]=c[x]+d;x=x+lowbit(x);}
}int main()
{int a[1001];int n, i, j;cin >> n;for(i=0; i<=n; i++ ){a[i]=i;}c[0]=0;for(i=1; i<=n; i++) //有a[]数组进行计算c[]数组的值{c[i]=0;for(j=i-lowbit(i)+1; j<=i; j++ ){c[i]=c[i]+a[j];} }int x;scanf("%d", &x);printf("%d\n", sum(x) ); //查询1->x的a[]的和int y;scanf("%d", &y);add(x, y); //a[]下标为x的元素增加dprintf("%d\n", sum(x));return 0;
}Sparse-Table：
范围最小值问题（RMQ）。给出一个n个元素的数组A1，A2，....，An，设计一个数据结构，支持查询操作Query（L,R）：计算min{A（l），A(l+1)，....，A(R)}。
d(i,j)表示从i开始的，长度为2的j次方的一小段元素中的最小值，所以d(i,j)=min{d(i,j-1),d(i+2的(j-1)次方，j-1)}。
#include<algorithm>
#define MAX 100000int n;
int d[MAX][50];
int A[MAX];void RMQ_init()
{for(int i=1;i<=n;i++)d[i][0]=A[i];for(int j=1;(1<<j)<=n;j++)for(int i=1;i+j-1<=n;i++)d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
}这样的话，查询操作很简单，令k为满足2的k次方<=R-L+1的最大整数，则以L开头，以R结尾的两个长度为2的k次方的区间合起来即覆盖了查询区间【L，R】。由于是取最小值，有些元素重复考虑了几遍也没关系。
int RMQ(int L,int R)
{int k=0;while((1<<(k+1))<=R-L+1)k++;return min(d[L][k],d[R-(1<<k)+1][k]);
}这个不需要完整模板了。。。初始化和查询都有了。
线段树：
线段树分为点更新和区间更新，但是点更新无非就是区间为1的区间更新，不过为了方便还是点和区间都放上去吧。线段树代码非常多，但是并不代表他复杂，无非是不断二分查找边界值。向上回溯更新，向下搜索更新。区间更新是设置一个数组保留要更新的值，用到了再去更新，大大节省时间。这个直接粘代码吧。参考了别人代码，因为我的丑https://blog.csdn.net/yyt330507870/article/details/70037135。
(0)定义
const int MAXN=50010;
int a[MAXN],ans[MAXN<<2],lazy[MAXN<<2];
//a[]为原序列信息，ans[]模拟线段树维护区间和，lazy[]为懒惰标记(1)更新结点信息
void PushUp(int rt)
{ans[rt]=ans[rt<<1]+ans[rt<<1|1];
}(2)建树
void Build(int l,int r,int rt)
{if (l==r){ans[rt]=a[l];return;}int mid=(l+r)>>1;Build(l,mid,rt<<1);Build(mid+1,r,rt<<1|1);PushUp(rt);
}(3) 下推懒惰标记
void PushDown(int rt,int ln,int rn)//ln表示左子树元素结点个数，rn表示右子树结点个数
{if (lazy[rt]){lazy[rt<<1]+=lazy[rt];lazy[rt<<1|1]+=lazy[rt];ans[rt<<1]+=lazy[rt]*ln;ans[rt<<1|1]+=lazy[rt]*rn;lazy[rt]=0;}
}(4)点更新
void Add(int L,int C,int l,int r,int rt)
{if (l==r){ans[rt]+=C;return;}int mid=(l+r)>>1;//PushDown(rt,mid-l+1,r-mid); 若既有点更新又有区间更新，需要这句话if (L<=mid)Add(L,C,l,mid,rt<<1);elseAdd(L,C,mid+1,r,rt<<1|1);PushUp(rt);
}(5)区间更新
void Update(int L,int R,int C,int l,int r,int rt)
{if (L<=l&&r<=R){ans[rt]+=C*(r-l+1);lazy[rt]+=C;return;}int mid=(l+r)>>1;PushDown(rt,mid-l+1,r-mid);if (L<=mid) Update(L,R,C,l,mid,rt<<1);if (R>mid) Update(L,R,C,mid+1,r,rt<<1|1);PushUp(rt);
}(6)区间查询
LL Query(int L,int R,int l,int r,int rt)
{if (L<=l&&r<=R)return ans[rt];int mid=(l+r)>>1;PushDown(rt,mid-l+1,r-mid);//若更新只有点更新，不需要这句LL ANS=0;if (L<=mid) ANS+=Query(L,R,l,mid,rt<<1);if (R>mid) ANS+=Query(L,R,mid+1,r,rt<<1|1);return ANS;
}(7)调用函数
//建树 Build(1,n,1); //点更新 Add(L,C,1,n,1); //区间修改 Update(L,R,C,1,n,1); //区间查询 int ANS=Query(L,R,1,n,1); 这东西虽然有模板，但是一定要理解，题里都有一定变换，熟练掌握才是硬道理。