线段树

基础数据结构
发布日期:   2021-09-28
更新日期:   2021-10-12
文章字数:   2k
阅读时长:   10 分
阅读次数:  

线段树

作用

  • 求解区间和
  • 求解区间最大值
  • 单点修改、区间修改
  • 扫描线、主席树

建树与懒标记下沉

//建树 
void built_tree(int l, int r, int now) {
    tree[now].l = l, tree[now].r = r;
    tree[now].cnt = r - l + 1; // 区间大小 
    tree[now].lazy = 0;
    if (l == r) {
        tree[now].sum = num[l];
        return ;
    }
    int mid = (l + r) >> 1;
    built_tree(l, mid, now << 1);
    built_tree(mid + 1, r, now << 1 | 1);
    PushUp(now);
    return ;
}
//懒标记下沉 
void down_lazy(int now) {
    if (tree[now].lazy == 0) return ;
    //懒标记下沉 
    tree[now << 1].lazy += tree[now].lazy;
    tree[now << 1 | 1].lazy += tree[now].lazy;
    //更新左右子树的区间和值 
    tree[now << 1].sum += tree[now].lazy * tree[now << 1].cnt;
    tree[now << 1 | 1].sum += tree[now].lazy * tree[now << 1 | 1].cnt;
    //懒标记重置 
    tree[now].lazy = 0;
    return ;
}

向上更新和值

// 向上更新和值 
void PushUp(int now) { 
    tree[now].sum = tree[now << 1].sum + tree[now << 1 | 1].sum;
}

区间修改

// 区间修改
void modify(int now, int l, int r, int lazy) {
    //修改区间完全包含该子树区间
    if (tree[now].l >= l && tree[now].r <= r) {
        tree[now].lazy += lazy;
        tree[now].sum += lazy * tree[now].cnt;
        return ;
    }
    // 向下分解区间前，先向下处理懒标记
    down_lazy(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    //左子树与修改区间有交集
    if (mid >= l) modify(now << 1, l, r, lazy);
    //右子树与修改区间有交集
    //mid + 1 <= r == mid < r
    if (mid < r) modify(now << 1 | 1, l, r, lazy);
    //回溯，更新区间和 
    PushUp(now);
    return ;
}

查询区间和

// 查询区间[l, r]的区间和
ll query(int now, int l, int r) {
    if (tree[now].l >= l && tree[now].r <= r) { //完全包含查询区间 
        return tree[now].sum;
    }
    // 向下分解区间前，向下处理懒标记先 
    down_lazy(now); 
    // 该节点区间二分
    int mid = (tree[now].l + tree[now].r) >> 1;
    ll tp_sum = 0;
       // 如果左子树区间与查询区间有交集，向左子树查询 
    if (mid >= l) tp_sum += query(now << 1, l, r);
    // 如果右子树区间与查询区间有交集，向右子树查询 
    // mid + 1 <= r == mid < r 
    if (mid < r) tp_sum += query(now << 1 | 1, l, r);
    // 返回查询区间的和 
    return tp_sum;
}

代码演示1

#include<stdio.h>

using namespace std;

typedef long long ll;
inline int read() {
    int w = 0, x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}
#define MAX_N 10002
struct Node {
    ll sum, lazy;  
    int l, r, cnt; // 区间左边界l，右边界r，区间元素个数cnt 
};

Node tree[MAX_N << 2]; // 存储树 
int num[MAX_N];

int n, m;

// 向上更新和值 
void PushUp(int now) { 
    tree[now].sum = tree[now << 1].sum + tree[now << 1 | 1].sum;
}
//建树 
void built_tree(int l, int r, int now) {
    tree[now].l = l, tree[now].r = r;
    tree[now].cnt = r - l + 1; // 区间大小 
    tree[now].lazy = 0;
    if (l == r) {
        tree[now].sum = num[l];
        return ;
    }
    int mid = (l + r) >> 1;
    built_tree(l, mid, now << 1);
    built_tree(mid + 1, r, now << 1 | 1);
    PushUp(now);
    return ;
}
//懒标记下沉 
void down_lazy(int now) {
    if (tree[now].lazy == 0) return ;
    //懒标记下沉 
    tree[now << 1].lazy += tree[now].lazy;
    tree[now << 1 | 1].lazy += tree[now].lazy;
    //更新左右子树的区间和值 
    tree[now << 1].sum += tree[now].lazy * tree[now << 1].cnt;
    tree[now << 1 | 1].sum += tree[now].lazy * tree[now << 1 | 1].cnt;
    //懒标记重置 
    tree[now].lazy = 0;
    return ;
}

// 查询区间[l, r]的区间和
ll query(int now, int l, int r) {
    if (tree[now].l >= l && tree[now].r <= r) { //完全包含查询区间 
        return tree[now].sum;
    }
    // 向下分解区间前，向下处理懒标记先 
    down_lazy(now); 
    // 该节点区间二分
    int mid = (tree[now].l + tree[now].r) >> 1;
    ll tp_sum = 0;
       // 如果左子树区间与查询区间有交集，向左子树查询 
    if (mid >= l) tp_sum += query(now << 1, l, r);
    // 如果右子树区间与查询区间有交集，向右子树查询 
    // mid + 1 <= r == mid < r 
    if (mid < r) tp_sum += query(now << 1 | 1, l, r);
    // 返回查询区间的和 
    return tp_sum;
}

// 区间修改
void modify(int now, int l, int r, int lazy) {
    //修改区间完全包含该子树区间
    if (tree[now].l >= l && tree[now].r <= r) {
        tree[now].lazy += lazy;
        tree[now].sum += lazy * tree[now].cnt;
        return ;
    }
    // 向下分解区间前，先向下处理懒标记
    down_lazy(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    //左子树与修改区间有交集
    if (mid >= l) modify(now << 1, l, r, lazy);
    //右子树与修改区间有交集
    //mid + 1 <= r == mid < r
    if (mid < r) modify(now << 1 | 1, l, r, lazy);
    //回溯，更新区间和 
    PushUp(now);
    return ;
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        num[i] = read();
    }
    built_tree(1, n, 1);
    for (int i = 1; i <= m; i++) {
        int t;
        t = read();
        if (t == 1) {
            int a, b, c;
            a = read(), b = read(), c = read();
            //if (b > c) continue;
            modify(1, a, b, c);
        } else {
            int a, b;
            a = read(), b = read();
            printf("%lld\n", query(1, a, b));
        }
    }
    return 0;
}

建树与更新最大值

//建树 
void built_tree(int l, int r, int now) {
    tree[now].l = l, tree[now].r = r;
    if (l == r) {
        tree[now].ma = num[l];
        return ;
    }
    int mid = (l + r) >> 1;
    built_tree(l, mid, now << 1);
    built_tree(mid + 1, r, now << 1 | 1);
    PushUp(now);
    return ;
}
// 向上更新子树最大值 
void PushUp(int now) {
    tree[now].ma = max(tree[now << 1].ma, tree[now << 1 | 1].ma);
}

单点修改

// 单点修改
void Update(int now, int l, int r, int pos, int val) {
    if (l == r) {
        tree[now].ma = val;
        return ;
    }
    int mid = (l + r) >> 1;
    if (mid >= pos) Update(now << 1, l, mid, pos, val);
    else Update(now << 1 | 1, mid + 1, r, pos, val);
    PushUp(now);
    return ;
}

区间查询最大值

// 区间查询
ll query(int now, int l, int r) {
    ll ma = -1;
    if (tree[now].l >= l && tree[now].r <= r) { //查询区间完全包含当前区间 
        ma = max(ma, tree[now].ma);
        return ma;
    }
    // 该节点区间二分
    int mid = (tree[now].l + tree[now].r) >> 1;
       // 如果左子树区间与查询区间有交集，向左子树查询 
    if (mid >= l) ma = max(query(now << 1, l, r), ma);
    // 如果右子树区间与查询区间有交集，向右子树查询 
    // mid + 1 <= r == mid < r 
    if (mid < r) ma = max(query(now << 1 | 1, l, r), ma);
    // 返回查询区间的和 
    return ma;
}

代码演示2

#include<stdio.h>

typedef long long ll;
inline int read() {
    int w = 0, x = 0;
    char ch = getchar();
    while (ch > '9' || ch < '0') {
        w |= ch == '-';
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return w ? -x : x;
}
#define MAX_N 10002
#define max(a, b) ((a) > (b) ? (a) : (b))

typedef struct Node {
    ll ma;  
    int l, r; // 区间左边界l，右边界r
} Node;

Node tree[MAX_N << 2]; // 存储树
int num[MAX_N];

int n, m;

// 向上更新子树最大值 
void PushUp(int now) { 
    tree[now].ma = max(tree[now << 1].ma, tree[now << 1 | 1].ma);
}
//建树 
void built_tree(int l, int r, int now) {
    tree[now].l = l, tree[now].r = r;
    if (l == r) {
        tree[now].ma = num[l];
        return ;
    }
    int mid = (l + r) >> 1;
    built_tree(l, mid, now << 1);
    built_tree(mid + 1, r, now << 1 | 1);
    PushUp(now);
    return ;
}


// 区间查询
ll query(int now, int l, int r) {
    ll ma = -1;
    if (tree[now].l >= l && tree[now].r <= r) { //查询区间完全包含当前区间 
        ma = max(ma, tree[now].ma);
        return ma;
    }
    // 该节点区间二分
    int mid = (tree[now].l + tree[now].r) >> 1;
       // 如果左子树区间与查询区间有交集，向左子树查询 
    if (mid >= l) ma = max(query(now << 1, l, r), ma);
    // 如果右子树区间与查询区间有交集，向右子树查询 
    // mid + 1 <= r == mid < r 
    if (mid < r) ma = max(query(now << 1 | 1, l, r), ma);
    // 返回查询区间的和 
    return ma;
}

// 单点修改
void Update(int now, int l, int r, int pos, int val) {
    if (l == r) {
        tree[now].ma = val;
        return ;
    }
    int mid = (l + r) >> 1;
    if (mid >= pos) Update(now << 1, l, mid, pos, val);
    else Update(now << 1 | 1, mid + 1, r, pos, val);
    PushUp(now);
    return ;
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i++) {
        num[i] = read();
    }
    built_tree(1, n, 1);
    for (int i = 1; i <= m; i++) {
        int t, a, b;
        t = read(), a = read(), b = read(); 
        if (t == 1) {
            if (a > b) continue;
            Update(1, 1, n, a, b);
        } else {
            if (a > b) {
                printf("-2147483648\n");
                continue;
            }
            printf("%lld\n", query(1, a, b));
        }
    }
    return 0;
}
文章作者: Axieyun
文章链接: https://Axieyun.top/posts/bdab.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Axieyun !
基础数据结构
赏
评论
评论
  目录