一、树状数组
在解题过程中，我们有时需要维护一个数组的前缀和 S[i]=A[1]+A[2]+...+A[i] 。但是不难发现，如果我们修改了任意一个 A[i],S[i] 、 S[i+1]...S[n] 都会发生变化。可以说，每次修改 A[i] 后，调整前缀和 S[] 在最坏情况下会需要 O(n) 的时间。当 n 非常大时，程序会运行得非常缓慢。因此，这里我们引入“树状数组”，它的修改与求和都是 O(logn) 的，效率非常高。
实现：
对于正整数x，定义lowbit（x）为x的二进制表达式中最右边的1所对应的值。
Lowbit(x)=x and -x对于节点i，如果它是左子节点，其父节点为i+lowbit(i)；
构造一个辅助数组C，其中Ci=Ai-lowbit(i)+1+Ai-lowbit(i)+2+…+Ai即C的每个元素都是A数组中的一段连续和。具体是每个灰色节点i都属于一个以它自身结尾的水平长条，这个长条中的数之和就是Ci。如C12=A9+A10+A11+A12=C10+A11+A12
如何更新C数组中的元素：如果修改了一个Ai，需要更新C数组中的哪些元素呢？从Ci开始往右走，边走边“往上爬”（不一定沿着树中的边爬），沿途修改所有结点对应的Ci即可。预处理时先把C数组清空，然后执行n次add操作。总时间为O（nlogn）
如何计算前缀和Si：顺着结点i往左走，边走边“往上爬”（不一定沿着树中的边爬），把沿途经过的Ci累加起来就可以了。对于query（L,R）=SR-SL-1。
代码：
var
b,c,f:array [0..100000] of longint;
ff,a:Array [0..100000] of boolean;
i,j,m,n,x,y,ans,l,r,tmp:longint;
s:string;
function dfs(x:longint):longint;
begin
if x<=1 then
exit;
c[f[x]]:=c[f[x]]+c[x];
dfs(f[x]);
end;
procedure dfs1(x:longint);
begin
dec(c[x]);
if x<=1 then
exit;
dfs1(f[x]);
end;
procedure dfs2(x:longint);
begin
inc(c[x]);
if x<=1 then
exit;
dfs2(f[x]);
end;
begin
readln(n);
fillchar(ff,sizeof(ff),true);
for i:=1 to n-1 do
begin
readln(x,y);
f[y]:=x;
inc(b[x]);
end;
for i:=1 to n do
c[i]:=1;
for i:=1 to n do
begin
if b[i]=0 then
dfs(i);
end;
readln(m);
for i:=1 to m do
begin
x:=0;
readln(s);
if s[1]=‘Q‘ then
begin
for j:=3 to length(s) do
x:=x*10+ord(s[j])-ord(‘0‘);
writeln(c[x]);
end;
if s[1]=‘C‘ then
begin
for j:=3 to length(s) do
x:=x*10+ord(s[j])-ord(‘0‘);
if ff[x] then
dfs1(x) else
dfs2(x);
ff[x]:=not ff[x];
end;
end;
End.
二、线段树
1,.线段树的结构:
区间：用一对数a和b表示一个前闭后开的区间[a,b)。（可以自己修改）结点T(a,b)：表示该结点维护了原数列中区间[a,b)的信息，其中a和b为整数且a<b内部结点：如果对于结点T(a,b)，有b-a>1，那么T(a,(a+b)/2)为T(a,b)的左孩子结点，T((a+b)/2,b)为T(a,b)的右孩子
叶结点：如果对于结点T(a,b)，有b-a=1，那么该结点就是叶结点线段树结构是递归定义的。
2.线段树的性质:
结点数：假设该线段树处理的数列长度为n，即根结点的区间为[1,n+1)，那么总结点个数不超过2*n个。深度：线段树可以近似看做一棵满二叉树，所以深度不超过log（2*n）线段分解数量级：线段树把区间上的任意一条长度为L的线段都分成了不超过2logL条线段，这使得大多数查询能够在O（logn）的时间内解决。
线段树的存储：
1、链表存储
2、数组模拟链表
3、堆结构存储
应用：
忠诚（loyal）
【问题描述】
老管家是一个聪明能干的人。他为财主工作了整整10年，财主为了让自已账目更加清楚。要求管家每天记k次账，由于管家聪明能干，因而管家总是让财主十分满意。但是由于一些人的挑拨，财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚，他把每次的账目按1，2，3…编号，然后不定时的问管家问题，问题是这样的：在a到b号账中最少的一笔是多少？为了让管家没时间作假他总是一次问多个问题。
在询问过程中账本的内容可能会被修改
【输入格式】
输入中第一行有两个数m,n表示有m(m<=100000)笔账,n表示有n个问题，n<=100000。
接下来每行为3个数字，第一个p为数字1或数字2，第二个数为x，第三个数为y
当p=1 则查询x,y区间
当p=2 则改变第x个数为y
【输出格式】
输出文件中为每个问题的答案。具体查看样例。
【输入样例】
10 3
1 2 3 4 5 6 7 8 9 10
1 2 7
2 2 0
1 1 10
【输出样例】
2 0
代码：
type
point=^node;
node=record
left,right:longint;
lp,rp:point;
sum:longint;
end;
var
p:array [1..100000] of node;
i,j,m,n,x,y,k:longint;
a:array [1..100000] of longint;
root:point;
procedure creat(p:point;l,r:longint);
begin
p^.left:=l; p^.right:=r; p^.sum:=maxlongint;
if l+1=r then
begin
p^.lp:=nil;
p^.rp:=nil;
end
else
begin
new(p^.lp); creat(p^.lp,l,(l+r) div 2);
new(p^.rp); creat(p^.rp,(l+r) div 2,r);
end;
end;
function min(x,y:longint):longint;
begin
if x<y then
exit(x);
exit(y);
end;
procedure update(p:point;x,delta:longint);
begin
if p^.left+1=p^.right then
begin
p^.sum:=delta;
end
else
begin
if x<(p^.left+p^.right) div 2 then
update(p^.lp,x,delta);
if x>=(p^.left+p^.right) div 2 then
update(p^.rp,x,delta);
p^.sum:=min(p^.lp^.sum,p^.rp^.sum);
end;
end;
function query(p:point;l,r:longint):longint;
var
ans:longint;
begin
if (l<=p^.left) and (p^.right<=r) then
exit(p^.sum);
ans:=maxlongint;
if l<(p^.left+p^.right) div 2 then
ans:=min(ans,query(p^.lp,l,r));
if r>(p^.left+p^.right) div 2 then
ans:=min(ans,query(p^.rp,l,r));
exit(ans);
end;
begin
readln(n,m);
for i:=1 to n do
read(a[i]);
new(root);
creat(root,1,n+1);
for i:=1 to n do
update(root,i,a[i]);
for i:=1 to m do
begin
readln(k,x,y);
if k=2 then
update(root,x,y);
if k=1 then
write(query(root,x,y+1),‘ ‘);
end;
writeln;
End.
版权声明：本文为博主原创文章，未经博主允许不得转载。
原文：http://blog.csdn.net/boyxiejunboy/article/details/46916847
