线段树

发表于 | 更新于 | 分类于 | 阅读次数：

联赛阶段比较万能的数据结构。

用结构体和指针来维护。

一个结构体大概长这样

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
struct NODE
{
	int l,r,tag,sum;
	NODE *ls,*rs;
	NODE(){ls=rs=nullptr;}
	NODE(const int &il,const int &ir,const int &s):l(il),r(ir),sum(s){tag=0,ls=rs=nullptr;}
	NODE& Update()
	{
		if(ls==nullptr)
		{
			return *this;
		}
		sum=ls->sum+rs->sum;
		return *this;
	}
	NODE& Push_Down()
	{
		if(ls!=nullptr)
		{
			ls->tag+=tag;
			ls->sum+=(ls->r-ls->l+1)*tag;
		}
		if(rs!=nullptr)
		{
			rs->tag+=tag;
			rs->sum+=(rs->r-rs->l+1)*tag;
		}
		tag=0;
		return *this;
	}
};

其中 Update和Push_Down分别是更新当前节点和下传懒标记（这个待会儿会说）。

两个构造函数对函数赋初值，并且为它建立两个指向左儿子与右儿子的节点（一开始指向空）。

然后是维护的区间左右端点，懒标记和维护的值。

建树

自底向上建树。

每次“合并”两个节点。

如果有剩余的一个，直接把他往上提一层。且他肯定不会有儿子节点了。

大概如此。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

void Build(int siz)
{
	NODE *a,*b,*t;
	queue <NODE*> remain,add;
	for(int i=1;i<=siz;i++)
	{
		t=new NODE(i,i,v[i]);
		remain.push(t);
	}
	for(;remain.size()>=2;Sonoda::swap(remain,add))
	{
		while(remain.size()>=2)
		{
			a=remain.front();
			remain.pop();
			b=remain.front();
			remain.pop();
			t=new NODE(a->l,b->r,a->sum+b->sum);
			t->ls=a;
			t->rs=b;
			t->Update();
			add.push(t);
		}
		if(!remain.empty())
		{
			t=remain.front();
			remain.pop();
			add.push(t);
		}
	}
	root=remain.front();
}

区间加

先下传再更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void Add(const int &l,const int &r,const int &t,NODE *NowNode)
{
	if(NowNode->l>r||NowNode->r<l)
	{
		return;
	}
	NowNode->Push_Down();
	if(NowNode->l>=l&&NowNode->r<=r)
	{
		NowNode->tag+=t;
		NowNode->sum+=(NowNode->r-NowNode->l+1)*NowNode->tag;
		return;
	}
	Add(l,r,t,NowNode->ls);
	Add(l,r,t,NowNode->rs);
	NowNode->Update();
}

####区间查

要下传。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int Query(const int &l,const int &r,NODE *NowNode)
{
	if(NowNode->l>r||NowNode->r<l)
	{
		return 0;
	}
	NowNode->Push_Down();
	if(NowNode->l>=l&&NowNode->r<=r)
	{
		return NowNode->sum;
	}
	return Query(l,r,NowNode->ls)+Query(l,r,NowNode->rs);
}