其实这两题都是基础的线段树，但对于我这个线段树的初学者来说，总结一下还是很有用的；
poj3468显然是线段树区间求和，区间更改的问题，而poj2528是对区间染色，问有多少种颜色的问题；
线段树的建立和求和附代码，还是比较简单的；
这里想说的是区间修改，用到了了lazy思想：打标记；
拿poj2528举例，比如对区间[l,r]染色，我们只要在线段树中，被[l,r]覆盖的最大子区间[p,q]上标记被染成了什么颜色即可，不需要再往下遍历[p,q]的左右孩子；当下次修改影响到了区间[p,q]时（区间有交集），说明[p,q]一定不会全都维持原来的颜色。我们将标记向下传递给左右孩子（同时自身标记清除），不断传递下去，直至某个区间完全被要修改区间覆盖，，再给这个区间打上新的标记。这样可保证时间复杂度为O(logn);
总之lazy思想的精髓就是，能不往下访问就不访问，要更改的时候再将子节点更改，从而减少时间复杂度；
var lazy,tree:array[..] of int64;
l,n,m,j,x,a,b,i:longint;
ans:int64;
c:char;
procedure pushdown(l,r,i:longint);
var m:longint;
begin
m:=(l+r) div ;
if lazy[i]= then exit;
lazy[i*]:=lazy[i*]+lazy[i];
lazy[i*+]:=lazy[i*+]+lazy[i];
tree[i*]:=tree[i*]+lazy[i]*(m-l+);
tree[i*+]:=tree[i*+]+lazy[i]*(r-m);
lazy[i]:=;
end; procedure build(i,l,r:longint);
var m:longint;
begin
if l=r then read(tree[i])
else begin
m:=(l+r) div ;
build(i*,l,m);
build(*i+,m+,r);
tree[i]:=tree[*i]+tree[*i+];
end;
end; function find(i,l,r,l1,r1:longint):int64;
var m:longint;
t:int64;
begin
if (l>=l1) and (r<=r1) then exit(tree[i])
else begin
pushdown(l,r,i);
m:=(l+r) div ;
t:=;
if l1<=m then t:=t+find(*i,l,m,l1,r1);
if r1>m then t:=t+find(*i+,m+,r,l1,r1);
exit(t);
end;
end; procedure work(i,l,r,l1,r1,x:longint);
var m:longint;
begin
if (l1<=l) and (r<=r1) then
begin
lazy[i]:=lazy[i]+x;
tree[i]:=tree[i]+(r-l+)*x;
end
else begin
pushdown(l,r,i);
m:=(l+r) div ;
if (l1<=m) then work(i*,l,m,l1,r1,x);
if (r1>m) then work(i*+,m+,r,l1,r1,x);
tree[i]:=tree[i*]+tree[i*+];
end;
end; begin
readln(n,m);
build(,,n);
readln;
fillchar(lazy,sizeof(lazy),);
for i:= to m do
begin
read(c);
if c='Q' then
begin
read(a,b);
ans:=find(,,n,a,b);
writeln(ans);
end
else if c='C' then
begin
read(a,b,j);
work(,,n,a,b,j);
end;
readln;
end;
end.
poj3468
而poj2528还要复杂一点，简单的建立线段树会爆空间，这需要我们把出现的区间离散化，减小空间复杂度。
var tree:array[..] of integer;
x,y:array[..] of longint;
a:array[..] of longint; //表示离散化乎的标号对应的区间
f:array[..] of boolean;
ff:array[..] of boolean;
i,j,k,n,t,s:longint;
procedure sort(l,r: longint);
var i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div ];
repeat
while a[i]<x do inc(i);
while x<a[j] do dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-;
end;
until i>j;
if l<j then sort(l,j);
if i<r then sort(i,r);
end;
procedure putdown(i,p,q:longint); //传递标记
begin
if p<>q then
begin
tree[i*]:=tree[i];
tree[i*+]:=tree[i];
tree[i]:=;
end;
end;
procedure build(i,p,q,l,r,x:longint);
var m:longint;
begin
if (a[p]>=l) and (r>=a[q]) then tree[i]:=x
else begin
if tree[i]<> then putdown(i,p,q);
m:=(p+q) div ;
if l<=a[m] then
begin
build(i*,p,m,l,r,x);
end;
if r>a[m] then
begin
build(i*+,m+,q,l,r,x);
end;
end;
end;
procedure dfs(i,p,q:longint); //统计多少可见海报
var m:longint;
begin
if (tree[i]>) and not ff[tree[i]] then
begin
s:=s+;
ff[tree[i]]:=true;
end
else if (tree[i]=) and (p<>q) then
begin
m:=(p+q) div ;
dfs(i*,p,m);
dfs(i*+,m+,q);
end;
end;
begin
readln(t);
for i:= to t do
begin
k:=;
fillchar(f,sizeof(f),false);
readln(n);
for j:= to n do
begin
readln(x[j],y[j]);
if not f[x[j]] then //离散化
begin
k:=k+;
a[k]:=x[j];
f[x[j]]:=true;
end;
if not f[y[j]] then
begin
k:=k+;
a[k]:=y[j];
f[y[j]]:=true;
end;
end;
sort(,k);
fillchar(tree,sizeof(tree),);
for j:= to n do
build(,,k,x[j],y[j],j);
s:=;
fillchar(ff,sizeof(ff),false);
dfs(,,k);
writeln(s);
end;
end.
poj2528
