风灵无畏OI
此站用来记录个人的OI成长史，以后会将个人做的每道题的解题报告发到此站上来，希望大家喜欢！（如有讲得不好的地方请大家指出，我会加以改进。当然也有可能传上来一点乱七八糟的东西）
注：转载文章请标上原址，毕竟码字很辛苦！谢谢！
线段树&树状数组（简la单ji版）
友情链接：https://liaoy148.lofter.com/post/1da8a74e_b09a15c
【题目】
T1：https://codevs.cn/problem/1080/
T2：https://codevs.cn/problem/1081/
T3：https://codevs.cn/problem/1082/
T4：https://codevs.cn/problem/2492/
【程序代码】
T1：https://code.csdn.net/snippets/2320344
T2：https://code.csdn.net/snippets/2320351
T3：https://code.csdn.net/snippets/2320362
T4：
【线段树】
线段树又叫区间树，他能够动态地取一个区间的合并数，能够很好地解决区间问题。
线段树是一棵二叉树，树中的每个节点表示了一个区间[a,b]，每个叶子节点表示了一个单位
区间。对于每一个非叶子结点所表示的节点[a,b],其左儿子表示的区间为[a,(a+b)/2]，右儿子表示
的区间为[(a+b)/2,b]。给每个节点增加一个域cover，当cover=1时，表示此区间被覆盖；当cove
r=0时，表示此区间没有被覆盖。根据树的性质，我们采用静态结构存储二叉树。
二叉树的存储：
type arr=record
l,r,sum,tag:int64;
end;
procedure build(p,l,r:int64);
var m:int64;
begin
tree[p].l:=l;
tree[p].r:=r;
if l<>r then
begin
m:=(l+r)shr 1;
build(p shl 1,l,m);
build(p shl 1+1,m+1,r);
end;
end;
二叉树的区间修改（单点修改可以看作为长度为1的区间）：
procedure change(p,l,r,data:int64);
var m:int64;
begin
if(tree[p].l=l)and(tree[p].r=r) then
begin
inc(tree[p].sum,(r-l+1)*data);
inc(tree[p].tag,data);
exit;
end;
push_down(p); //下面会做解释
m:=(tree[p].l+tree[p].r)shr 1;
if r<=m then change(p shl 1,l,r,data)
else if m+1<=l then change(p shl 1+1,l,r,data)
else
begin
change(p shl 1,l,m,data);
change(p shl 1+1,m+1,r,data);
end;
tree[p].sum:=tree[p shl 1].sum+tree[p shl 1+1].sum;
end;
二叉树的区间求和（单点查询可以看作为长度为1的区间）：
function getsum(p,l,r:int64):int64;
var m:int64;
begin
if(tree[p].l=l)and(tree[p].r=r) then exit(tree[p].sum);
push_down(p); //下面会做解释
m:=(tree[p].l+tree[p].r)shr 1;
if r<=m then exit(getsum(p shl 1,l,r))
else
if l>=m+1then exit(getsum(p shl 1+1,l,r))
else
begin
exit(getsum(p shl 1,l,m)+getsum(p shl 1+1,m+1,r));
end;
end;
二叉树的lazy tag
作用：lazy tag 就是用来记录当前更改的区间的值，这样就不用每次都递归到最底层，可以节约时间。
procedure push_down(p:int64);
begin
if tree[p].tag=0 then exit;
inc(tree[p shl 1].sum,tree[p].tag*(tree[p shl 1].r-tree[p shl 1].l+1));
inc(tree[p shl 1+1].sum,tree[p].tag*(tree[p shl 1+1].r-tree[p shl 1+1].l+1));
inc(tree[p shl 1].tag,tree[p].tag);
inc(tree[p shl 1+1].tag,tree[p].tag);
tree[p].tag:=0;
end;
线段树还可以做查询最大值（C++版）
void ins(int k,int nl,int nr,int l,long long x){
if(nl==nr){
sum[k]+=x;maxx[k]+=x;
return;
}
int mid=(nl+nr)>>1;
if(l<=mid)ins(k<<1,nl,mid,l,x);
else ins(k<<1|1,mid+1,nr,l,x);
sum[k]=sum[k<<1]+sum[k<<1|1];
maxx[k]=max(maxx[k<<1],maxx[k<<1|1]);
}//因为自己以前没写过，就直接搬学长的代码了QWQ。其实只要在记录类型中加一个maxx来记录当前得到的最大值，然后再把“ maxx[k]=max(maxx[k<<1],maxx[k<<1|1]); ”这句改一下便可
//大概就是这些吧QWQ
【树状数组】
树状数组其实就是把数组弄成了一个树状的，然后关键就是lowbit函数的运用（具体可见《奥赛经典——数据结构篇》-向期中编著)
这里也贴两个题吧：
T1：https://www.luogu.org/problem/show?pid=3374
T2：https://www.luogu.org/problem/show?pid=3368//这个用到了差分数组
程序代码
T1：https://code.csdn.net/snippets/2320414
T2：https://code.csdn.net/snippets/2320413
树状数组包括以下几个部分：
一、lowbit 函数//lowbit函数主要是用来求十进制数x对应的二进制末尾0的个数
function lowbit(x:longint):longint;
begin
exit(x and(-x));
end;
二、改变某一个值
procedure change(x,data:longint);
begin
while x<=n do
begin
inc(f[x],data);
inc(x,lowbit(x));
end;
end;
三、求和
function getsum(x:longint):longint;
begin
while x<>0do
begin
inc(getsum,f[x]);
dec(x,lowbit(x));
end;
end;
具体的就这三个吧，是不是感觉比线段树容易多了？（但是，线段树能用的地方多多了，有些题是只能用线段树做，而不能用树状数组做QWQ）