本篇只用于我对树状数组和线段树的初步思考记录
树状数组：
对于tr[i]，存储的是[i-(i&-i)+1,i]的数的信息。比如4的二进制为100，存储的就是[01,100]2的信息，6的二进制为110，存储的是[101,110]的信息。
对于[1,r]范围的区间查询，用-=i&-i表示对r的二进制位全部分解，得到结果，如r=7时，二进制表示为111，则这段区间信息就是111的信息+110的信息+100的信息+000的信息，再如r=1012时，区间信息应为101+100+000，当r=1011时，区间信息为1011+1010+1000+0000
对于[i]的单点修改，即让最低位1的位置不断提高以覆盖全部包含该数字的区间
对于[l,r]的区间修改，由于树状数组的结构问题，必须将其转化为俩个单点修改，然后用前缀和求区间修改，这时就不便使用树状数组
所以树状数组用于简单的前缀和查询是比线段树要好很多的，但这里要注意的是，前缀和由于可以进行逆运算（sum[r]-sum[l-1]=sum[l,r]）可以维护任意区间，但是最大值或者gcd是不支持右区间减左区间去维护任意[l,r]的范围，只能维护[1,r]的范围。因此，树状数组只能维护类似加法，异或，乘法（无0）的任意区间，对于最大值，最小值，gcd，lcm，之类的只能维护前缀信息。
总结：树状数组本质上是维护前缀信息的结构。要查询任意区间 [ l , r ] 的信息，通常需要该信息满足可逆性（即可以通过两个前缀信息组合得到区间信息）。
单点修改代码如下：
查看代码
struct BIT {int n;vector<int> c;BIT(int n_) : n(n_ + 1), c(n_ + 1, 0) {}//初始化int sum(int r) {int s = 0;while (r > 0) s += c[r], r -= r & -r;return s;}//左区间查询int sum(int l, int r) {if (l > r) return 0;return sum(r) - sum(l - 1);}//区间查询void add(int idx, int delta) {while (idx < n) c[idx] += delta, idx += idx & -idx;}//点修
};下标线段树：
线段树是基于二分思想的一种数据结构，相对与树状数组，线段树可以通过懒标记来维护区间修改，以及区间信息，在功能上比树状数组要更胜一筹。
线段树每个节点对应一个区间的汇总信息，因此要求区间之间满结合律。难点在于维护懒标记和区间合并的数学关系推导
先看建树过程：
可以用id<<1和id<<1|1这样朴素的建树方式，每个节点的结构体内变量l,r分别维护该节点表示的左右范围；
也可以用动态开点的方式（n>=1e8），在函数的传递过程中传递区间l，r；
以下是俩种建树方式的代码，可以自行比较
查看代码
void build(int id,int l,int r){tr[id]={l,r,a[l],1,0};if(l>=r)return;int md=(l+r)>>1;build(lc,l,md);build(rc,md+1,r);pushup(id);//这个地方如果不需要维护类似最值的条件就可以直接注释掉
}
/*
动态开点一般不会有建树函数，只有在用到的时候才会建节点，洛谷p13825模版题
*/
void add(int &id,int l,int r,int x,int y,int k){//if(!id)id=++idx;if(x<=l && r<=y){tr[id].sum+=k*(r-l+1);tr[id].add+=k;return;}pushdown(id,l,r);int md=(l+r)>>1;if(x<=md)add(lc,l,md,x,y,k);if(y>md)add(rc,md+1,r,x,y,k);pushup(id);
}