本文共 3607 字，大约阅读时间需要 12 分钟。

建树

$a$数组为初始数组，$tree$数组为树

typedef long long ll;const int inf = 0x7fffffff;const int maxn = 2e5 + 10;int a[maxn];int tree[maxn << 2], lz[maxn << 2];

建树函数

和普通线段树唯一的区别就是更新时取左右子树的最值

void build(int i, int l, int r) {     //i传入1    if (l == r) {           tree[i] = a[l];        return;    }    int mid = (l + r) >> 1, k = i << 1;    build(k, l, mid);    build(k | 1, mid + 1, r);    tree[i] = max(tree[k], tree[k | 1]);}

单点修改

函数功能：将位置$x$的值修改为$y$

因为没有用结构体保存区间的左右边界$l,r$，因此需要传入修改的总区间$[l,r]=[1,n]$

void update(int i, int l, int r, int x, int y) {       if (l == r) {   	    tree[i] = y;	    return;	}	int mid = (l + r) >> 1, k = i << 1;	if (x <= mid) update(k, l, mid, x, y);	else update(k | 1, mid + 1, r, x, y);	tree[i] = max(tree[k], tree[k | 1]);}

区间加法

懒惰标记

使用数组$lz$记录向子区间都加的值，$pushdown$时只需要将子节点的值和标记都加上父节点的标记，然后清空父节点的标记。

void pushdown(int i) {       if (lz[i]) {           int k = i << 1;        tree[k] += lz[i], tree[k | 1] += lz[i];        lz[k] += lz[i], lz[k | 1] += lz[i], lz[i] = 0;    }}

区间加法

将区间$[x,y]$都加上$val$。

void add(int i, int l, int r, int x, int y, int val) {       if (l == x && r == y) {           tree[i] += val, lz[i] += val;        return;    }    pushdown(i);    int mid = (l + r) >> 1, k = i << 1;    if (x > mid) add(k | 1, mid + 1, r, x, y, val);    else if (y <= mid) add(k, l, mid, x, y, val);    else add(k, l, mid, x, mid, val), add(k | 1, mid + 1, r, mid + 1, y, val);    tree[i] = max(tree[k], tree[k | 1]);}

区间查询

函数功能：查询区间$[x,y]$的最值。

有三种情况：

• 如果被修改区间完全在左区间
• 如果被修改区间完全在右区间
• 如果都不在，就要把修改区间分解成两块，分别往左右区间递归

int query(int i, int l, int r, int x, int y) {       if (x <= l && y >= r) return tree[i];    pushdown(i);    int mid = (l + r) >> 1, k = i << 1;	if (y <= mid) return query(k, l, mid, x, y);	else if (x > mid) return query(k | 1, mid + 1, r, x, y);	return max(query(k, l, mid, x, y), query(k | 1, mid + 1, r, x, y));}

简单模板

typedef long long ll;const int inf = 0x7fffffff;const int maxn = 2e5 + 10;int a[maxn];int tree[maxn << 2], lz[maxn << 2];inline int max(int a, int b) {    return a > b ? a : b; }void build(int i, int l, int r) {       if (l == r) {           tree[i] = a[l];        return;    }    int mid = (l + r) >> 1, k = i << 1;    build(k, l, mid);    build(k | 1, mid + 1, r);    tree[i] = max(tree[k], tree[k | 1]);}void update(int i, int l, int r, int x, int y) {       if (l == r) {           tree[i] = y;        return;    }    int mid = (l + r) >> 1, k = i << 1;    if (x <= mid)        update(k, l, mid, x, y);    else        update(k | 1, mid + 1, r, x, y);    tree[i] = max(tree[k], tree[k | 1]);}void pushdown(int i) {       if (lz[i]) {           int k = i << 1;        tree[k] += lz[i], tree[k | 1] += lz[i];        lz[k] += lz[i], lz[k | 1] += lz[i], lz[i] = 0;    }}void add(int i, int l, int r, int x, int y, int val) {       if (l == x && r == y) {           tree[i] += val, lz[i] += val;        return;    }    pushdown(i);    int mid = (l + r) >> 1, k = i << 1;    if (x > mid) add(k | 1, mid + 1, r, x, y, val);    else if (y <= mid) add(k, l, mid, x, y, val);    else add(k, l, mid, x, mid, val), add(k | 1, mid + 1, r, mid + 1, y, val);    tree[i] = max(tree[k], tree[k | 1]);}int query(int i, int l, int r, int x, int y) {       if (x <= l && y >= r) return tree[i];    pushdown(i);    int mid = (l + r) >> 1, k = i << 1;    if (y <= mid)        return query(k, l, mid, x, y);    else if (x > mid)        return query(k | 1, mid + 1, r, x, y);    return max(query(k, l, mid, x, y), query(k | 1, mid + 1, r, x, y));}