线段树解析题型
线段树的作用(线段树适合些什么题型)
1.最小值、最大值、总和
2.区间更新的最小值、最大值、总和等等
线段树基本知识
如果你拥有并且知道上节课的知识你写此类题目,你将如鱼得水,
因为下面块引用认真解析了此次解题的函数的意思
【全网最强解析】--线段树--C语言/C++-CSDN博客
https://blog.csdn.net/q20202828/article/details/146291630?spm=1001.2014.3001.5501线段树_哔哩哔哩_bilibili
A Simple Problem with Integers
你有 N 个整数，A1、A2、... 、AN。您需要处理两种作。一种类型的作是在给定的时间间隔内将一些给定的数字添加到每个数字。另一种是询问给定区间内的数字之和。
输入
第一行包含两个数字 N 和 Q。1 ≤ N，Q ≤ 100000。
第二行包含 N 个数字，初始值为 A1、A2、... 、AN。-10000000000 ≤ A ≤ 1000000000。
接下来的 Q 行中的每一行都表示一个作。
“C abc” 是指将 c 添加到 Aa、Aa+1、... 、Ab 中的每一个。-10000 ≤ c ≤ 10000。
“Q ab” 表示查询 Aa， Aa+1， ... ， Ab 之和。
输出
您需要按顺序回答所有 Q 命令。一行中只有一个答案。
样本
| 输入复制 | 输出复制 |
|---|---|
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
| 4
55
9
15 |
提示
总和可能超出 32 位整数的范围。
代码如下
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 1e5 + 5;
long long n, m, q[MAXN], a, b, c, d;
struct node {
long long date, lazy;
}tree[MAXN * 4];
void build(long long date[], long long rt, long long left, long long right) {
if (left == right) {
tree[rt].date = date[left];
return;
}
long long mid = left + (right - left) / 2;
build(date, 2 * rt, left, mid);
build(date, 2 * rt + 1, mid + 1, right);
tree[rt].date = tree[rt * 2].date + tree[rt * 2 + 1].date;
}
void pushDown(int rt, int left, int right) {
if (tree[rt].lazy == 0) return;
int mid = left + (right - left) / 2;
tree[rt * 2].date += tree[rt].lazy * (mid - left + 1);
tree[rt * 2].lazy += tree[rt].lazy;
tree[rt * 2 + 1].date += tree[rt].lazy * (right - mid);
tree[rt * 2 + 1].lazy += tree[rt].lazy;
tree[rt].lazy = 0;
}
long long query(long long rt, long long left, long long right, long long ql, long long qr) {
if (ql > right || qr < left) {
return 0;
}
if (ql <= left && qr >= right) {
return tree[rt].date;
}
long long mid = left + (right - left) / 2;
pushDown(rt, left, right);
long long leftNum = query(rt * 2, left, mid, ql, qr);
long long rightNum = query(rt * 2 + 1, mid + 1, right, ql, qr);
return leftNum + rightNum;
}
void updateRange(long long rt, long long left, long long right, long long ql, long long qr, long long value) {
if (ql > right || qr < left) {
return;
}
if (ql <= left && qr >= right) {
tree[rt].date += value * (right - left + 1);
tree[rt].lazy += value;
return;
}
long long mid = left + (right - left) / 2;
pushDown(rt, left, right);
updateRange(2 * rt, left, mid, ql, qr, value);
updateRange(rt * 2 + 1, mid + 1, right, ql, qr, value);
tree[rt].date = tree[rt * 2].date + tree[rt * 2 + 1].date;
}
int main() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &q[i]);
}
build(q, 1, 1, n);
while (m--) {
scanf("%d", &d);
if (d == 2) {
scanf("%lld%lld", &a, &b);
printf("%lld\n", query(1, 1, n, a, b));
}
else if (d == 1) {
scanf("%lld%lld%lld", &a, &b, &c);
updateRange(1, 1, n, a, b, c);
}
}
return 0;
}B - 线段树 1
描述
如题，已知一个数列 {ai}{ai}，你需要进行下面两种操作：
- 将某区间每一个数加上 kk。
- 求出某区间每一个数的和。
输入
第一行包含两个整数 n,mn,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 nn 个用空格分隔的整数 aiai，其中第 ii 个数字表示数列第 ii 项的初始值。
接下来 mm 行每行包含 33 或 44 个整数，表示一个操作，具体如下：
1 x y k：将区间 [x,y][x,y] 内每个数加上 kk。2 x y：输出区间 [x,y][x,y] 内每个数的和。
输出
输出包含若干行整数，即为所有操作 2 的结果。
示例 1
| 输入复制 | 输出复制 |
|---|---|
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4 | 11
8
20 |
提示
对于 15%15% 的数据：n≤8n≤8，m≤10m≤10。
对于 35%35% 的数据：n≤103n≤103，m≤104m≤104。
对于 100%100% 的数据：1≤n,m≤1051≤n,m≤105，ai,kai,k 为正数，且任意时刻数列的和不超过 2×10182×1018。
【样例解释】
代码如下
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN = 1e5 + 5;
long long n, m, q[MAXN],a,b,c,d;
struct node{
long long date, lazy;
}tree[MAXN*4];
void build(long long date[], long long rt, long long left, long long right) {
if (left == right) {
tree[rt].date = date[left];
return;
}
long long mid = left + (right - left) / 2;
build(date, 2 * rt, left, mid);
build(date, 2 * rt + 1, mid + 1, right);
tree[rt].date = tree[rt * 2].date + tree[rt * 2 + 1].date;
}
void pushDown(int rt, int left, int right) {
if (tree[rt].lazy == 0) return;
int mid = left + (right - left) / 2;
tree[rt * 2].date += tree[rt].lazy * (mid - left + 1);
tree[rt * 2].lazy += tree[rt].lazy ;
tree[rt * 2 + 1].date += tree[rt].lazy * (right - mid);
tree[rt * 2 + 1].lazy += tree[rt].lazy;
tree[rt].lazy = 0;
}
long long query(long long rt, long long left, long long right, long long ql, long long qr) {
if (ql > right || qr < left) {
return 0;
}
if (ql <= left && qr >= right) {
return tree[rt].date;
}
long long mid = left + (right - left) / 2;
pushDown(rt,left,right);
long long leftNum = query(rt * 2, left, mid, ql, qr);
long long rightNum = query(rt * 2 + 1, mid + 1, right, ql, qr);
return leftNum + rightNum;
}
void updateRange(long long rt, long long left, long long right, long long ql, long long qr, long long value) {
if (ql > right || qr < left) {
return;
}
if (ql <= left && qr >= right) {
tree[rt].date += value * (right - left + 1);
tree[rt].lazy += value;
return;
}
long long mid = left + (right - left) / 2;
pushDown(rt,left,right);
updateRange(2 * rt, left, mid, ql, qr, value);
updateRange(rt * 2 + 1, mid + 1, right, ql, qr, value);
tree[rt].date = tree[rt * 2].date + tree[rt * 2 + 1].date;
}
int main() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%lld", &q[i]);
}
build(q, 1, 1, n);
char ch;
while (m--) {
scanf(" %c", &ch);
if (ch == 'Q') {
scanf("%lld%lld", &a, &b);
printf("%lld\n", query(1, 1, n, a, b));
}
else if (ch == 'C') {
scanf("%lld%lld%lld", &a, &b, &c);
updateRange(1, 1, n, a, b, c);
}
}
return 0;
}