Fork me on GitHub

线段树

发表于
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。

线段树 模板

1
2
3
4
5
struct xdtree
{
    int maxx;
    int delta;
}tree[4*maxn];

直接修改每个叶节点值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void updata(int left,int right,int root)
{
	int mid;
	if(y<left||x>right)
		return;
	if(x<=left&&y>=right)
	{
		tree[root].maxx+=k;
		tree[root].delta++;
		return;
	}
	mid=(left+right)/2;
	int delta=tree[root].delta;
	tree[root*2].maxx+=delta;tree[root*2].delta+=delta;
	tree[root*2+1].maxx+=delta;tree[root*2+1].delta+=delta;
	tree[root].delta=0;
	updata(left,mid,root*2);
	updata(mid+1,right,root*2+1);
	tree[root].maxx=max(tree[root*2].maxx,tree[root*2+1].maxx);
}

查询

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int search(int left,int right,int root)
{
	int mid,tr,tl;
	if(y<left||x>right)
		return -222222222;
	if(x<=left&&y>=right)
		return tree[root].maxx;
	mid=(left+right)/2;
	int delta=tree[root].delta;
	tree[root*2].maxx+=delta;tree[root*2].delta+=delta;
	tree[root*2+1].maxx+=delta;tree[root*2+1].delta+=delta;
	tree[root].delta=0;
	tl=search(left,mid,root*2);
	tr=search(mid+1,right,root*2+1);
	return max(tr,tl);
}

将区间内叶子节点加上k

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    int delta=tree[root].delta;  //根的偏移量。

    //往左右子树传递偏移量

         tree[root*2].delta+=delta;

         tree[root*2].maxx+=delta;

         tree[root*2+1].maxx+=delta;

         tree[root*2+1].delta+=delta;

         tree[root].delta=0;   //因为偏移量已经往下传，当前根的偏移量清0.
```        
我们来对比一下，加K与直接更新相比，就多了如上一段代码，这段代码就是线段树思想的核心：偏移量顺便往下传递。相应修改的值也要做一下修改。

ATTENTION
只有一个大区间的答案可以从左右两个小区间的答案中合并而来时，才可以用线段树。反之，如果一个大区间的答案不可以从左右两个小区间的答案中合并而来时，线段树就失去了意义。