A Simple Problem with Integers 【线段树】

题目链接POJ-3468

[kuangbin带你飞]专题七 线段树

题目描述

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.


思路

区间修改,询问区间和。 典型的线段树板子题;
易错
1.需要用到lazy标记
2.数据范围可能会爆int, 数据类型开 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
#include <iostream>
using namespace std;

#define MAX 100010

struct Node{
long long l, r;
long long sum, lazy;
void updata(long long val)
{
sum += (r - l + 1) * val;
lazy += val;
}
}tree[MAX * 4];

void push_up(int k)
{
tree[k].sum = tree[k<<1].sum + tree[k<<1|1].sum;
}

void push_down(int k)
{
long long lazyval = tree[k].lazy;
if(lazyval)
{
tree[k<<1].updata(lazyval);
tree[k<<1|1].updata(lazyval);
tree[k].lazy = 0;
}
}

void build(int k, int l, int r)
{
tree[k].l = l, tree[k].r = r;
tree[k].sum = tree[k].lazy = 0;
if(l == r)
{
cin >> tree[k].sum;
}
else
{
int mid = (l + r) >> 1;
build(k<<1, l, mid);
build(k<<1|1, mid+1, r);
push_up(k);
}
}

void updata(int k, int l, int r, long long val)
{
int L = tree[k].l, R = tree[k].r;
if(l <= L && R <= r)
{
tree[k].updata(val);
}
else
{
push_down(k);
int mid = (L + R) >> 1;
if(l <= mid)
updata(k<<1, l, r, val);
if(mid < r)
updata(k<<1|1, l, r, val);
push_up(k);
}
}

long long query(int k, int l, int r)
{
int L = tree[k].l, R = tree[k].r;
if(l <= L && R <= r)
{
return tree[k].sum;
}
else
{
long long tmp = 0;
push_down(k);
int mid = (L + R) >> 1;
if(l <= mid)
tmp += query(k<<1, l, r);
if(mid < r)
tmp += query(k<<1|1, l, r);
push_up(k);
return tmp;
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m;
while(cin >> n >> m)
{
build(1, 1, n);
for(int i = 1; i<=m; i++)
{
string s;
cin >> s;
if(s == "Q")
{
int x, y;
cin >> x >> y;
cout << query(1, x, y) << endl;
}
else
{
long long x, y, val;
cin >> x >> y >> val;
updata(1, x, y, val);
}
}
}
return 0;
}
-------------本文结束,感谢您的阅读!-------------