POJ_3468_线段树延迟标记

POJ 3468

  • 当需要区间修改而不是单点修改时.如果仍用单点修改来修改区间的所有点.必超时
  • 若修改区间为[l,r],且覆盖节点p的[e[p].left,e[p].right].为了避免修改子树所有节点(可能修改了后都用不到,浪费时间).
  • 修改该节点的区间值,且标记,当我们需要递归到子树时,在来一层一层更新
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <string.h>
using namespace std;
const int maxn = 1e5+5;

struct segementTree {
	int l,r;
	long long sum,add;
	#define left(x) tree[x].l
	#define right(x) tree[x].r
	#define sum(x) tree[x].sum
	#define add(x) tree[x].add
} tree[4*maxn];
int num[maxn];
int n,m;

void build(int p,int left,int right) {
	left(p) = left; right(p) = right;
	if (left == right) {
		sum(p)=num[left];
		return ;
	}
	int mid = (left + right)/2;
	build(2*p,left,mid);
	build(2*p+1,mid+1,right);
	sum(p) = sum(p*2) + sum(p*2+1);
	return ;
}
void spread(int p) {
	if (add(p)) { // 线段树中p点是否有标记
		sum(p*2) += add(p)*(right(p*2) - left(p*2) + 1); //更新左子树的区间值
		sum(p*2+1) += add(p)*(right(p*2+1) - left(p*2+1) + 1); //
		add(p*2) += add(p); // 给左子树标记
		add(p*2+1) += add(p);
		add(p) = 0; //消除p点(子树根节点)标记 
	}
}

void change(int p,int left,int right,int val) {
	if (left <=left(p) && right(p)<=right) {
		sum(p) += (long long)val * (right(p) - left(p) + 1); //先更新该区间的线段树节点的和
		add(p) += (long long)val; // 延迟标记
		return ;
	}
	// 没有完全覆盖,说明需要向下递归
	spread(p); // 向下传递延迟标记
	int mid = (left(p) + right(p))/2;
	if (left <= mid) change(2*p,left,right,val);
	if (right > mid) change(2*p+1,left,right,val);
	sum(p) = sum(p*2) + sum(p*2+1); 
}

long long ask(int p,int left,int right) {
	if (left <= left(p) && right(p) <= right) return sum(p);
	spread(p);
	int mid = (left(p) + right(p))/2;
	long long val = 0;
	if (left <= mid) val += ask(2*p,left,right);
	if (right > mid) val += ask(2*p+1,left,right);
	return val;
}

int main() {
//	freopen("a.txt","r",stdin);
	cin >> n >> m;
	for (int i=1; i<=n; i++) scanf("%d",&num[i]);
	build(1,1,n);
	char ch[2]; int u,v,w;
	for (int i=1; i<=m; i++) {
		scanf("%s%d%d",ch,&u,&v);
		if (ch[0] == 'Q') 
			printf("%lld\n",ask(1,u,v));	
		else {
			scanf("%d",&w);
			change(1,u,v,w);
		}
	}
	return 0;
}
算法
延迟标记

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！