线段树

博主： Solost
发布时间：2023 年 04 月 10 日
186 次浏览
暂无评论
599字数
分类： ACM笔记

## 概念

线段树是算法竞赛中常用的用来维护 **区间信息** 的数据结构。

线段树可以在`O(log N)`的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

## 操作

1. 定义树
2. pushdown
3. pushup
4. build
5. modify
6. query

### 定义树

```cpp
struct node {
    int l, r;
    ll sum, add;
} tr[N * 4]; //经过推导，需要开四倍

```

### pushdown

```cpp
void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add) {
        left.add += root.add, left.sum += ll(left.r - left.l + 1) * root.add;
        right.add += root.add, right.sum += ll(right.r - right.l + 1) * root.add;
        root.add = 0;
	/*
	更新过程中需要把父节点的懒标记更新到子节点
	子节点继承父节点的懒标记，并更新自己的sum值
	删除父节点的懒标记
	*/
    }
}
```

### pushup

```cpp
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    //将父节点的sum更新，记得要直接=，而不是+=
}
```

### build

```cpp
void build(int u, int l, int r)
{
    if (l == r) {
        tr[u] = { l, r, w[l], 0 };
    } else {
        tr[u] = { l, r };
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}
```

### midify

```cpp
void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].sum += ll(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
    } else {
        pushdown(u);//因为要把一个区间分开，所以要往下穿懒标记
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (mid >= l)
            modify(u << 1, l, r, d);
        if (mid < r)
            modify(u << 1 | 1, l, r, d);
        pushup(u);//修改完以后要把子节点的值更新到父节点
    }
}
```

### query

```cpp
ll query(int u, int l, int r)
{

if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].sum;

ll sum = 0;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid)
        sum += query(u << 1, l, r);
    if (mid < r)
        sum += query(u << 1 | 1, l, r);

return sum;
}
```

## 例题

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F04%2F10%2Fimage.png)

### 例题链接

[链接](https://www.acwing.com/problem/content/244/)

### 题解

```cpp
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;
#define x first
#define y second
#define endl '\n'
#define IOS                       \
    ios_base::sync_with_stdio(0); \
    cin.tie(0);                   \
    cout.tie(0);
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int n, m;
int w[N];
struct node {
    int l, r;
    ll sum, add;
} tr[N * 4];

void pushdown(int u)
{
    auto &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
    if (root.add) {
        left.add += root.add, left.sum += ll(left.r - left.l + 1) * root.add;
        right.add += root.add, right.sum += ll(right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

void build(int u, int l, int r)
{
    if (l == r) {
        tr[u] = { l, r, w[l], 0 };
    } else {
        tr[u] = { l, r };
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int l, int r, int d)
{
    if (tr[u].l >= l && tr[u].r <= r) {
        tr[u].sum += ll(tr[u].r - tr[u].l + 1) * d;
        tr[u].add += d;
    } else {
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if (mid >= l)
            modify(u << 1, l, r, d);
        if (mid < r)
            modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

ll query(int u, int l, int r)
{

if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].sum;

ll sum = 0;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid)
        sum += query(u << 1, l, r);
    if (mid < r)
        sum += query(u << 1 | 1, l, r);

return sum;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> w[i];

build(1, 1, n);
    while (m--) {
        char op;
        int l, r, d;
        cin >> op;
        if (op == 'Q') {
            cin >> l >> r;
            cout << query(1, l, r) << endl;
        } else {
            cin >> l >> r >> d;
            modify(1, l, r, d);
        }
    }
}
int main()
{
    // IOS;
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
```

最后修改：2023 年 04 月 10 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

线段树

Solost • 2023 年 04 月 10 日

## 概念

线段树是算法竞赛中常用的用来维护 **区间信息** 的数据结构。

线段树可以在`O(log N)`的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

## 操作

1. 定义树
2. pushdown
3. pushup
4. build
5. modify
6. query

### 定义树

```cpp
struct node {
    int l, r;
    ll sum, add;
} tr[N * 4]; //经过推导，需要开四倍

```

### pushdown

### pushup

```cpp
void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
    //将父节点的sum更新，记得要直接=，而不是+=
}
```

### build

### midify

### query

```cpp
ll query(int u, int l, int r)
{

if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].sum;

ll sum = 0;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid)
        sum += query(u << 1, l, r);
    if (mid < r)
        sum += query(u << 1 | 1, l, r);

return sum;
}
```

## 例题

![image.png](https://amarantos.oss-cn-hangzhou.aliyuncs.com/typecho/2023%2F04%2F10%2Fimage.png)

### 例题链接

[链接](https://www.acwing.com/problem/content/244/)

### 题解

const int INF = 0x3f3f3f3f, mod = 1000000007;
const int N = 2e5 + 10;
int n, m;
int w[N];
struct node {
    int l, r;
    ll sum, add;
} tr[N * 4];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

ll query(int u, int l, int r)
{

if (tr[u].l >= l && tr[u].r <= r)
        return tr[u].sum;

ll sum = 0;
    pushdown(u);
    int mid = (tr[u].l + tr[u].r) >> 1;
    if (l <= mid)
        sum += query(u << 1, l, r);
    if (mid < r)
        sum += query(u << 1 | 1, l, r);

return sum;
}

void solve()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> w[i];

线段树

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛（同步赛) -F-坐火车

树状数组

动态规划

Codeforces Round 712 (Div. 1) - B. 3-Coloring

2023牛客寒假算法基础集训营2 L-Tokitsukaze and Three Integers

Codeforces Round 578 (Div. 2) - E. Compress Words

Prime

动态规划

AcWing - 1562. 微博转发

大数据期末

线段树

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

线段树

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款