线段树就像树状数组一样，通过将一个长为n的段落，划分为O(logn)个子段落，这样就可以通过维护子段落的属性，来求得整个段落的属性。可以证明，任何一个子段在一颗线段树上不会被划分为超过2logn个子段。
一个典型的线段树如下：
线段树的实现可以采用数组静态实现，就像二叉堆一样，每个节点则维护了一个子段的相关属性。也可以采用动态实现，即采用动态内存分配。线段树的关键在找到什么属性来用线段树维护，为了维护这个属性，每个节点该包含那些信息。而在这样的结构下如何完成插入，删除和查询。
count color来自http://acm.pku.edu.cn/JudgeOnline/problem?id=2777
在考虑其实现时，很明显的应该将 color作为一个属性，但是该问题，由于存在一个更新问题，而且更新的时候是一个段而不是某个点，这样导致与普通的实现不同。如何在O(logn)时间内完成C 操作，成为关键。另一方面，由于该颜色数目小于30，因此可以考虑采用int的位表示颜色几何，因为这样可以方便的利用位并求合集。
而在更新时，如果我们考虑保证所有的节点都正确地代表的段内的颜色的集合，这样将导致所需的更新操作远远增加，以如下［1，8］为例，我们要更新它，则涉及到其所有父亲，以及其所有孩子，极端情况下就会需要O(n)个子段要更新。所以这样更新不现实，另一方面，考虑线段树，是否可以只更新那些组成该线段的子段呢？
如果仅更新子段，而仍然按照普通的查询是不可以的，因为我们无法保证查询时候比如区间为[1,4]，我们更新[1,2],如果进行染色时，我们只更新[1,2]这个节点，而不更新其子节点，而当我们查询[2,3]时，需要[2]这个点，如果我们还是按照原来的查询方法，即把[2,3]分成［2］［3］,实际上就会得到那个未被更新的节点[2]的颜色了，这样就是不行的了。
但是我们只要稍加变化，即在查询某个段时，如果发现它是某个段的子段，而该段只有一个颜色，那么我们就可以终止不必往下进行了。比如上面的[2,3]我们在线段树上分裂到了[1,2]发现[2]包含在[1,2]并且［1，2］是单色的，那么我们就不必往下找了。如果这样查询，我们就可以在更新时只需更新那些子段，同时注意更新这些子段的父亲就可以了，不必再往下更新到所有的子节点了。
综上，我们实现时要注意两个事情，更新时，要进行必要的往下往上更新，其中往下更新指在节点为单色时，同时更新子结点的颜色，以防止该节点被染回原色。向上更新，指更新父节点的颜色，insert最后一句即是。参见红色代码部分。
而查询时要注意：一旦发现单色节点，则返回。红色代码部分
//数组静态实现
#include <cstdio>
#include<algorithm>
using namespace std;
#define MAX_N 300003
//segement tree
int seg[MAX_N];
int bin_exp[32];
void init(){
for(int i = 0 ; i < 32 ; i++){
bin_exp[i] = 1 << i;
}
}
void build(int node,int begin,int end,int col){
seg[node] = col;
if(begin == end){
return;
}
build(2*node,begin,begin+(end-begin)/2,col);
build(2*node+1,begin+(end-begin)/2+1,end,col);
}
bool is_single(int x){
return (x&(x-1))== 0;
}
void insert(int node,int begin,int end,int left,int right,int col){
if(left > end || right < begin) return;
if(begin >= left && end <= right){seg[node] = col;return;}
//如果当前点颜色与要染的色相同，当然不必再染色
if(seg[node] == col)return;
/*
注意这句的作用，是为了防止最后 seg[node] = seg[2*node] | seg[2*node+1];又把seg[node]的颜色还原，比如我们更新[1,2]时，如果[1,2]被调用了，而我们在更新时不对其子节点同时更新，那么最后 seg[node] = seg[2*node] | seg[2*node+1];就会把我们[1,2]的颜色染回原色。
*/
if(is_single(seg[node])){
seg[2*node] = seg[2*node+1] = seg[node];
}
insert(2*node,begin,begin+(end-begin)/2,left,right,col);
insert(2*node+1,begin+(end-begin)/2+1,end,left,right,col);
//必须进行更新，这样才能保证父亲是对的，即如果我们对[1,2]染色了，必须同时更新它的那些父亲节点，即包含它的段。
seg[node] = seg[2*node] | seg[2*node+1];
}
int color = 0;
void query(int node,int begin,int end,int left,int right){
//如果当前区间与查询区间不相交，同时意味着后面的执行都是相交的那些段
if(begin > right || end < left)return;
if(begin >= left && end <= right){color |= seg[node];return;}
//很明显，如果当前是单色的，则结果是显然的，不用再看了
if(is_single(seg[node])){color |= seg[node];return;}
query(2*node,begin,begin+(end-begin)/2,left,right);
query(2*node+1,begin+(end-begin)/2+1,end,left,right);
}
int cal(int n){
int cnt=0;
while(n>0){
if(n%2) cnt++;
n>>=1;
}
return cnt;
}
int main(){
int L,T,O;
scanf("%d%d%d",&L,&T,&O);
build(1,1,L,1);
char cmd[10];
int s,e,c;
while(O--){
scanf("%s",&cmd);
if(cmd[0]=='C'){
scanf("%d%d%d",&s,&e,&c);
if(s>e) swap(s,e);
insert(1,1,L,s,e,1<<(c-1));
}
else if(cmd[0]=='P'){
color=0;
scanf("%d%d",&s,&e);
if(s>e) swap(s,e);
query(1,1,L,s,e);
printf("%d\n",cal(color));
}
}
return 0;
}
//参考实现，动态版本
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define MAXN 100001
struct Seg_Tree{
Seg_Tree *leftptr,*rightptr;
int left,right;
int col;
}*Root;
int L,T,O,cnt;
int nmem;
Seg_Tree mem[MAXN*10];
Seg_Tree* CreateNode(){
Seg_Tree* p=&mem[nmem++];
memset(p,0,sizeof(Seg_Tree));
return p;
}
Seg_Tree* CreateTree(int s,int e){
Seg_Tree* root=CreateNode();
root->left=s;
root->right=e;
if(s!=e){
int mid=(s+e)/2;
root->leftptr=CreateTree(s,mid);
root->rightptr=CreateTree(mid+1,e);
}
return root;
}
bool odd(int n){//判断奇偶的，其实就判断是不是只有一种颜色。
return (n&(n-1))==0;
}
void UpdateTree(Seg_Tree* root,int s,int e,int c){
//printf("update:(%d %d) ",root->left,root->right);
if(s<=root->left&&e>=root->right){
root->col=c;
return;
}
if(root->col==c) return;
if(odd(root->col)){
root->leftptr->col=root->col;
root->rightptr->col=root->col;
}
int mid=(root->left+root->right)/2;
if(s<=mid) UpdateTree(root->leftptr,s,e,c);
if(e>mid) UpdateTree(root->rightptr,s,e,c);
root->col=root->leftptr->col|root->rightptr->col;
}
void Query(Seg_Tree* root,int s,int e,int &cnt){
if(s<=root->left&&e>=root->right){
//printf("query:(%d %d) ",root->left,root->right);
cnt=cnt|root->col;
return;
}
if(odd(root->col)){
cnt=cnt|root->col;
return;
}
int mid=(root->left+root->right)/2;
if(s<=mid) Query(root->leftptr,s,e,cnt);
if(e>mid) Query(root->rightptr,s,e,cnt);
}
int color = 0;
void query(Seg_Tree* root,int s,int e){
if(e < root->left || s > root->right)return;
if(s == root->left && e == root->right) {
// printf("found.%d",root->col);
color= root->col;
return;
}
int mid=(root->left+root->right)/2;
if(s<=mid) query(root->leftptr,s,e);
if(e>mid) query(root->rightptr,s,e);
}
//void printf
int cal(int n){
int cnt=0;
while(n>0){
if(n%2) cnt++;
n>>=1;
}
return cnt;
}
int main(){
nmem=0;
scanf("%d%d%d",&L,&T,&O);
Root=CreateTree(1,L);
UpdateTree(Root,1,L,1);
char cmd[10];
int s,e,c;
while(O--){
scanf("%s",&cmd);
if(cmd[0]=='C'){
scanf("%d%d%d",&s,&e,&c);
if(s>e) swap(s,e);
UpdateTree(Root,s,e,1<<(c-1));
}
else if(cmd[0]=='P'){
cnt=0;
scanf("%d%d",&s,&e);
if(s>e) swap(s,e);
Query(Root,s,e,cnt);
printf("%d\n",cal(cnt));
}
else{
color = 0;
scanf("%d%d",&s,&e);
query(Root,s,e);
}
}
return 0;
}
评论