【POJ-3468】解题报告（线段树求和，区间维护）

原始题目

A Simple Problem with Integers

  • Time Limit: 5000MS
  • Memory Limit: 131072K
  • Total Submissions: 129411
  • Accepted: 40139
  • Case Time Limit: 2000MS

Description

You have N integers, A1, A2, ... , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.

Input

The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000. The second line contains N numbers, the initial values of A1, A2, ... , AN. -1000000000 ≤ Ai ≤ 1000000000. Each of the next Q lines represents an operation. "C a b c" means adding c to each of Aa, Aa+1, ... , Ab. -10000 ≤ c ≤ 10000. "Q a b" means querying the sum of Aa, Aa+1, ... , Ab.

Output

You need to answer all Q commands in order. One answer in a line.

Sample Input

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

Sample Output

4
55
9
15

Hint

The sums may exceed the range of 32-bit integers.

Source

POJ Monthly--2007.11.25, Yang Yi

题目大意

对于一组序列A,有两种操作，询问：给出对应区间序列的和，增加：给出对应区间区间内所有点增加固定值。

解题思路

线段树模板题，区间询问，区间修改，注意long long即可。

解题代码

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <string>
#include <set>
#include <queue>
#include <vector>
#include <map>
using namespace std;
const int maxn=2e5+5;
typedef long long ll;
ll n,m;
ll d,x;
ll b,e;
ll a[maxn];
struct node
{
	ll l;
	ll r;
	ll sum;
	ll tag;
	ll maxnum;
}tree[maxn<<2];

char ch[2];

void build(ll k,ll l,ll r) //k为线段树的角标 
{
	tree[k].l=l;
	tree[k].r=r;
	if(l==r)
	{
		tree[k].sum=a[l]=a[r];  //叶子节点，单点的sum即是本身 
		return ; 
	}
	ll mid=(l+r)>>1;
	build(k<<1,l,mid); //递归构建左线段（左子树） 
	build(k<<1|1,mid+1,r);	//递归构建右线段（右子树） 
	tree[k].sum=tree[k<<1].sum+tree[k<<1|1].sum; 
	return ; 
}

void change1(ll k,ll d,ll x)
{
	if(tree[k].l==tree[k].r&&tree[k].r==d) //找到索引点 
	{
		tree[k].maxnum=x; //修改最大值
		return ; 
		//修改后再开始回溯 
	} 
	ll mid=(tree[k].l+tree[k].r)>>1;
	if(d>=tree[k].l&&d<=mid) //查找点在左子树
		change1(k<<1,d,x); //k<<1为左子树,
	else //查找点在右子树， 
		change1(k<<1|1,d,x); //k<<1|1为右子树
	tree[k].maxnum=max(tree[k<<1].maxnum,tree[k<<1|1].maxnum);  //递归从新计算非叶结点的值 
}

void change(ll k) //懒惰操作，有标记才操作一次，有记忆性 
{
	if(tree[k].l==tree[k].r)
		tree[k].sum+=tree[k].tag;
	else 
	{
		tree[k].sum+=(tree[k].r-tree[k].l+1)*tree[k].tag;
		tree[k<<1].tag+=tree[k].tag;
		tree[k<<1|1].tag+=tree[k].tag;
		 
	}
	tree[k].tag=0; //自身标记清零 
}

void add(ll k,ll l,ll r,ll x)
{
	if(tree[k].tag)
	{
//		printf("--");
		change(k);
	}
	if(tree[k].l==l&&tree[k].r==r)  //在固定的区间打标记 
	{
		tree[k].tag+=x; //向下打标记 
//		printf("k=%lld l=%lld r=%lld tag=%lld\n",k ,l,r,tree[k].tag);
		return ; 
	}
//	printf("1  %lld\n",tree[k].sum);
	tree[k].sum+=(r-l+1)*x;
//	printf("2  %lld\n",tree[k].sum);
	ll mid=(tree[k].r+tree[k].l)>>1;
	if(r<=mid)
		add(k<<1,l,r,x);
	else if(l>=mid+1)
		add(k<<1|1,l,r,x);
	else 
	{
		add(k<<1,l,mid,x);
		add(k<<1|1,mid+1,r,x); 	
	}
}


ll query(ll k,ll l,ll r)
{
//	printf("query %lld .tag=%lld\n",k,tree[k].tag);
	if(tree[k].tag)
	{
//		printf("$");
		change(k); 
	}
		

	ll mid=(tree[k].l+tree[k].r)>>1;
	if(tree[k].l==l&&tree[k].r==r)
		return tree[k].sum;
	if(r<=mid)
		return query(k<<1,l,r);
	else if(l>=mid+1)
		return query(k<<1|1,l,r);
	else 
		return query(k<<1,l,mid)+query(k<<1|1,mid+1,r); //中线跨区间 

}


int main()
{
	while(~scanf("%lld%lld",&n,&m))
	{
		memset(tree,0,sizeof(tree));
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
		}
		build(1,1,n);
		
		for(ll i=1;i<=m;i++)
		{
			scanf("%s",ch);
			if(ch[0]=='Q')
			{
				scanf("%lld%lld",&b,&e);
//				printf("11");
				printf("%lld\n",query(1,b,e));
			}
			else 
			{
				scanf("%lld%lld%lld",&b,&e,&x);
				add(1,b,e,x);
			}
		}
		
	}
}

收获与反思

  • 注意数组不要越界，注意long long。
  • 写模板注意sum的写法和取最大值的写法略有不同。
  • 理解lazy（tag）标记，即访问到时才进行一次向下扩展，每次修改并不直接作用于叶子节点。