看到hjw初一神线段树辣么6，于是默默又去复（xue）习（xi）了一下线段树。
线段树大概的原理什么的就不讲了。放个模板就好。（可能注释会比较多）
我线段树有个风格... 先说下 i<<1 的意思是 i*2
(i<<1) or 1 的意思是 i*2+1
注释有错麻烦说下~~~
type node=record l,r:longint;//节点区间[l,r] sum:int64;//节点的信息，这里指和 flag:longint;//懒惰标记 end; var tree:array[0..800000]of node;//线段树 ans:int64;//答案 i:longint; x,d,a,b,p:longint; n,m:longint; procedure changesum(i:longint);//上推过程更改节点的信息 begin tree[i].sum:=tree[i<<1].sum+tree[i<<1 or 1].sum; end; procedure build(i:longint;l,r:longint);//建树，以节点i为根，l,r是总区间 var m:longint;//二分思想的中间值 begin tree[i].l:=l; tree[i].r:=r; if tree[i].l=tree[i].r then //到达叶子节点，可以回溯了 begin exit; end; m:=(l+r)>>1;//中间值 build(i << 1,l,m); //向左儿子建树 build((i << 1) or 1,m+1,r);//向右儿子建树 changesum(i);//回溯更改节点信息 end; procedure down(i:longint);//下推 var l,r,lnum,rnum:longint; begin l:=i<<1; //左儿子 r:=i<<1 or 1; //右儿子 lnum:=tree[l].r-tree[l].l +1; //左儿子包含的数的个数 rnum:=tree[r].r-tree[r].l +1; //右儿子包含的数的个数 inc(tree[l].flag,tree[i].flag); //向左儿子下推懒惰标记 inc(tree[r].flag,tree[i].flag); //向右儿子下推懒惰标记 inc(tree[l].sum,tree[i].flag*lnum); //更新左儿子信息 inc(tree[r].sum,tree[i].flag*rnum); //更新右儿子信息 tree[i].flag :=0; //懒惰标记清零 end; procedure aski(i:longint;x:longint); //单点查询, i 为当前节点, x 为查询的下标, var m:longint; begin if tree[i].l=tree[i].r then //到叶子节点，可以返回值 begin ans:=tree[i].sum; //储存在 ans(全局变量) 中 exit; end; if tree[i].flag<>0 then down(i); //有懒惰标记要下推 m:=(tree[i].l+tree[i].r)>>1; //中间值 if x<=m then aski(i<<1,x) else aski(i<<1 or 1,x); //二分查找 x end; procedure changei(i,d,x:longint); //单点修改, i 为当前节点, d 为修改值, x 为修改的下标 var m:longint; begin if tree[i].l=tree[i].r then //到叶子节点，可以修改了 begin inc(tree[i].sum,d); exit; end; m:=(tree[i].l+tree[i].r)>>1; if x<=m then changei(i<<1,d,x) else changei(i<<1 or 1,d,x); //查找 x 节点 changesum(i); //回溯更改节点信息 end; procedure asklr(i:longint;a,b:longint); //查询区间 i 为当前节点 a,b 为查询的[l,r]区间 var m:longint; begin if (tree[i].l>=a)and(tree[i].r<=b) then //有一个节点的区间能包含[l,r]（这里的 a,b ）区间 begin inc(ans,tree[i].sum); exit; end; if tree[i].flag<>0 then down(i); //下推咯 m:=(tree[i].l+tree[i].r)>>1; if a<=m then asklr(i<<1,a,b); if b>m then asklr(i<<1 or 1,a,b); end; procedure changelr(i,a,b,d:longint); //更改区间 i为当前节点 a 为 l b 为 r d 为修改值 var m:longint; begin if (tree[i].l>=a)and(tree[i].r<=b) then begin inc(tree[i].sum,(tree[i].r-tree[i].l+1)*d); inc(tree[i].flag,d); //记得懒惰标记咯 exit; end; if tree[i].flag<>0 then down(i); //下推咯 m:=(tree[i].l+tree[i].r)>>1; if a<=m then changelr(i<<1,a,b,d); if b>m then changelr(i<<1 or 1,a,b,d); changesum(i); end; begin build(1,1,n); // 以1为根, [l,r]区间就是[1,n]
aski(1,x); // 从根节点 1 开始找, 查询为 x 下标的信息
changei(1,d,x); //从根节点 1 开始找, 修改值为 d , 修改 x 下标
asklr(1,l,r); //从根节点 1 开始找, 查询 l,r 区间
changelr(1,l,r,d) //从根节点 1 开始找 修改 l,r 区间 修改值d
end.
练习什么的以后再来。