wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

算法基础搜索数据结构字符串数学图论动态规划计算几何杂项

数据结构

线段树

线段树单点修改

线段树区间修改

可持久化线段树

树链剖分

平衡树

FHQ-Treap

[[ item.c ]]

线段树区间修改

线段树区间修改同样是针对**单群**而言，这里引入一个**映射集** $$ F $$，满足
$$(F: S \to S,  S \times S \to S,  e \in S)$$

$$F$$ 中存在一个恒等映射 $$\text{id}(x)$$，满足对于所有 $$x \in S$$，有 $$\text{id}(x) = x$$  成立
	
*  满足闭包，即对于 $$f, g \in F$$，那么 $$f \circ g \in F$$

*  积性，对于操作 `*`，（可以在 `op` 操作中定义），对于 $$x, y \in S$$
   我们有 $$f(x \* y) = f(x) * f(y)$$
   
一般而言，线段树区间修改需要执行以下操作
* 求一个区间 `[l, r]` 中 `op(a[l], ..., a[r])` 的结果

* 对区间 `[l, r]` 中的所有元素 `x` 执行映射 $$x \to f(x), f \in F$$

## 构造函数和方法

```bash
(1) lazy_segtree<S, op, e, F, mapping, composition, id> seg(int n);
(2) lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<T> v);
```

* `S, op, e` 和单点修改的一样
`S` 表示节点元素类型，`op`对应`pull`操作，`e`是幺元

* `F`是**映射的类型**，或者说是**懒标记的数据类型**

比如让区间都加上一个数，`F <=> long long`
  因为用 `long long add` 即可表示区间加运算
  如果涉及两种以上操作，比如区间加，区间乘，那么`F`可以定义为一个**结构体**
  ```
  struct F {
  	long long mul, add;
  };
  ```

* 
`mapping` 是映射规则，形式为 `S mapping(F f, S x)`，返回 $$f(x)$$
 值得注意的是，这里的`F f`表示什么？
 可以理解为`f`是**线段树懒标记**，可以是 `add, mul,...` 等等
 `F` 为**懒标记的类型**，可以看作懒标记**作用到**区间上
 
 比如让区间所有数都`+d`，`d`是一个`long long`型
 那么就可以声明，对于 $$x$$ 节点表示的区间，执行 $$x \to f(x)$$

```bash
	// 仅执行区间加法
	struct S {
		long long sum, len;
		// 维护区间和，区间长度
	};
	S mapping(long long f, S x) {
		return S{x.sum + f*x.len, x.len};
	}
	```
	 容易看出，`mapping`实际上规定了一个区间怎么打**懒标记**
 
*

`composition` 规定了 $$f\circ g$$ 的规则
 
  假设只有一种操作，比如就是区间加，考虑 `F composition(F f1, F f2)`
  如果懒标记是`long long`类型的，就是 `ll compositon(ll f1, ll f2)`
  表示的意义是，先加上懒标记`f2`，再加上`f1`，可以如下声明

```bash
	long long composition(long long f1, long long f2) {
		return f1 + f2;
	}
	```
  
  **复杂的复合操作**如下，比如我们需要同时执行区间加和区间乘，规定

```bash
	struct F {
		long long mul, add;
	};
	S mapping(F f, S x) {
		return S{ x.sum*f.mul + x.len*f.add,   x.len };
	};
	```
> 说明，注意如果同时有加法和乘法两种操作
只有加法的时候，我们可以定义变换 `F f(1, add)`
只有乘法的时候，类似定义变换 `F f(mul, 0)`，这样两种操作可以**统一起来**
区间重新赋值为 `val` 可以定义变换 `F f(0, val)`

> 那么对于复合操作`(F f, F g)`，$$f\circ g$$ 可以如下声明

> 
$$g(x) = x\cdot g.mul + g.add \\\ f(g(x)) = (x\cdot g.mul) \cdot f.mul + (f.add + f.mul \cdot g.add)$$

> 
 ```
 F composition(F f, F g) {
 	return F{ f.mul*g.mul, f.mul*g.add+f.add };
 }
 ```
	
* `F id()` 定义了恒等变换
  如果同时有加法和乘法两种操作，那么恒等变换就是

```bash
	F id() {
	  return F{1, 0};
	}
	
	// x = x*1 + 0
	```
	
## 区间修改和区间查询
### 区间查询

**set, get**

```bash
void seg.set(int p, S x)
S seg.get(int p)
```
将区间 $$a[p] \to x$$，返回区间 $$a[p]$$

**prod**

`S seg.prod(int l, int r)`
返回 `op( a[l], a[l+1], ..., a[r-1] )` 的结果，如果 `l = r`，返回 `e()`

**all_prod**

`S seg.all_prod()`
 返回 `op( a[0], a[1], ..., a[n-1] )` 的结果，如果 `n = 0` 返回 `e()`
 
 ### 区间修改
 
 **apply**
 
 ```bash
 (1)  void seg.apply(int p, F f)
 (2)  void seg.apply(int l, int r, F f)
 ```
 执行单点修改，区间修改，特别地
 区间修改，对所有的 `i = [l, l+1, ..., r-1]`，执行 $$a[i] \to f(a[i])$$
 
 **max_right**
 
 ```bash
 (1)  int seg.max_right<g> (int l)
 (2)  int seg.max_right<G> (int l, G g)
 ```
 或者还可以写成
 ```bash
 (3)  int seg.max_right<g> (int l, int r)
 ```
 
 * `G` 是一个函数对象，一般来说，返回的是一个 `bool` 类型
 * 必须定义 `bool g(S x)`，并执行线段树上二分，`S` 是线段树的节点数据类型
 
该函数的返回值是 `pos`，用于在区间 `[l, r]` 中查找一个位置 `pos`，满足
*  `g( op(a[l], a[l+1], ..., a[pos-1]) ) = true`，但是
*  `g( op(a[l], a[l+1], ..., a[pos-1], a[pos]) ) = false`

换句话说，我们要找到**第一个不满足**某个性质的位置，即第一个 `g() = false` 的位置
如果找不到，返回 `-1`

**min_left**

`int seg.min_left<g> (int l, int r)`

函数返回值是一个 `pos`，用于在区间 `[l, r]` 中查找一个位置 `pos`，满足

*  `g( op(a[r], a[r-1], ..., a[pos]) ) = true`，但是
*  `g( op(a[r], a[r-1], ..., a[pos], a[pos-1]) ) = false`

换句话说，我们要往左找到最左边**最后一个满足**某个性质的位置，即往左最后一个 `g() = true` 的位置
如果找不到，返回 `-1`

## 一些例子
给定 $$a_1, a_2, \cdots, a_n$$，我们要支持 `q` 个操作
* `1 l r d`，给区间 `[l, r]` 所有数都加上 `d`

* `2 l r d`，给区间 `[l, r]` 所有数都乘上 `d`
* `3 l r d`，给区间 `[l, r]` 所有数赋值为 `d`

* `4 l r`，查询 `[l, r]` 的区间和，对 $$10^9 + 7$$ 取模

**算法实现**

```bash
// 定义线段树节点
struct S {
    mint sum;
    int len;
};

S op(S a, S b) {
    S res;
    res.sum = a.sum + b.sum;
    res.len = a.len + b.len;
    return res;
}

S e() {
    return S{0, 0};
}
// 定义懒标记及映射规则
struct F {
    mint mul, add;
};

S mapping(F f, S x) {
    S res;
    res.sum = x.sum * f.mul + f.add * mint(x.len);
    res.len = x.len;
    return res;
}

F composition(F f, F g) {
    return F{
        f.mul*g.mul,
        f.mul*g.add + f.add
    };
}

F id() {
    return F{1, 0};
}

int main() {
    int n, q;
    scanf("%d%d", &n, &q);
    // 部分代码省略

lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);
    while (q--) {
        int op;
        scanf("%d", &op);

if (op == 1) {
            int l, r, d;
            scanf("%d%d%d", &l, &r, &d);
            l -= 1;

seg.apply(l, r, F{mint(1), mint(d)});
        }
		// 其他代码省略
    }
}
```

## 线段树懒标记模版

```bash
namespace Seg {

template<class S,
        S (*op)(S, S),
        S (*e)(),
        class F,
        S (*mapping)(F, S),
        F (*composition)(F, F),
        F (*id)()>
class lazy_segtree {
public:
    lazy_segtree() : lazy_segtree(0) {}
    explicit lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {}
    explicit lazy_segtree(const std::vector<S> &v) : _n(int(v.size())) {
        size = 4 * _n;
        node = std::vector<S>(size, e());
        lz = std::vector<F>(size, id());

function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l >= r) {
                node[p] = v[l];
                return;
            }
            int mid = (l + r) >> 1;
            build(p<<1, l, mid), build(p<<1|1, mid+1, r);
            pull(p);
        };

build(1, 0, _n-1);
    }

// a[p] = x;
    void set(int p, S x) {
        assert(0 <= p && p < _n);
        change(1, 0, _n-1, p, x);
    }

S get(int p) {
        assert(0 <= p && p < _n);
        return query(1, 0, _n-1, p, p);
    }

S prod(int l, int r) {
        assert(0 <= l && l <= r && r <= _n);
        return query(1, 0, _n-1, l, r-1);
    }

S all_prod() const { return node[1]; }

void apply(int l, int r, F f) {
        assert(0 <= l && l <= r && r <= _n);
        modify(1, 0, _n-1, l, r-1, f);
    }

void apply(int p, F f) {
        assert(0 <= p && p < _n);
        modify(1, 0, _n-1, p, p+1, f);
    }

// return p in [l, r], satisfy:
    // g( op(a[l], a[l+1], ..., a[p-1]) ) = true
    // g( op(a[l], a[l+1], ..., a[p]) ) = false
    // -1 we cannot find such p, in other words
    // we want to find first postion that f() = false

template<bool (*g)(S)>
    int max_right(int l, int r) {
        return max_right(1, 0, _n-1, l, r, [](S x) { return g(x); });
    }

template<bool (*g)(S)>
    int min_left(int l, int r) {
        return min_left(1, 0, _n-1, l, r, [](S x) { return g(x); });
    }

private:
    int _n, size;
    std::vector<S> node;
    std::vector<F> lz;

void pull(int p) {
        node[p] = op(node[p<<1], node[p<<1|1]);
    }

inline void all_apply(int p, F f) {
        node[p] = mapping(f, node[p]);
        lz[p] = composition(f, lz[p]);
    }

inline void push(int p) {
        all_apply(p<<1, lz[p]), all_apply(p<<1|1, lz[p]);
        lz[p] = id();
    }

void change(int p, int l, int r, int pos, S x) {
        if (l >= r) {
            node[p] = x;
            return;
        }
        int mid = (l + r) >> 1;
        push(p);

if (pos <= mid) change(p<<1, l, mid, pos, x);
        else change(p<<1|1, mid+1, r, pos, x);

pull(p);
    }

void modify(int p, int l, int r, int ql, int qr, F f) {
        if (ql == l && r == qr) {
            node[p] = mapping(f, node[p]);
            lz[p] = composition(f, lz[p]);
            return;
        }
        int mid = (l + r) >> 1;
        push(p);

if (qr <= mid) modify(p<<1, l, mid, ql, qr, f);
        else if (ql > mid) modify(p<<1|1, mid+1, r, ql, qr, f);
        else {
            modify(p<<1, l, mid, ql, mid, f);
            modify(p<<1|1, mid+1, r, mid+1, qr, f);
        }
        pull(p);
    }

S query(int p, int l, int r, int ql, int qr) {
        if (ql == l && r == qr) return node[p];
        int mid = (l + r) >> 1;

push(p);

if (qr <= mid) return query(p<<1, l, mid, ql, qr);
        else if (ql > mid) return query(p<<1|1, mid+1, r, ql, qr);
        else {
            return op(query(p<<1, l, mid, ql, mid),
                    query(p<<1|1, mid+1, r, mid+1, qr));
        }
    }

// return p <= qr, satisfy:
    // g( op(a[ql], a[ql+1], ..., a[p-1]) ) = true
    // g( op(a[ql], a[ql+1], ..., a[p]) ) = false
    // -1, we cannot find such p
    // we want to find first position f() = false;

template<class G>
    int max_right(int p, int l, int r, int ql, int qr, G g) {
        assert(0 <= l && l <= _n);
        if (ql == _n) return _n;
        if (ql == l && r == qr) {
            if (g(node[p])) return -1;
            if (l == r) return l;

int mid = (l + r) >> 1;
            push(p);
            if (!g(node[p<<1])) return max_right(p<<1, l, mid, ql, mid, g);
            else return max_right(p<<1|1, mid+1, r, mid+1, qr, g);
        }

int mid = (l + r) >> 1;
        push(p);
        if (qr <= mid) return max_right(p<<1, l, mid, ql, qr, g);
        else if (ql > mid) return max_right(p<<1|1, mid+1, r, ql, qr, g);
        else {
            int pos = max_right(p<<1, l, mid, ql, mid, g);
            if (pos != -1) return pos;
            else return max_right(p<<1|1, mid+1, r, mid+1, qr, g);
        }
    }

// find p
    // g( op(a[qr], a[qr-1], ..., a[p]) ) = true
    // g( op(a[qr], a[qr-1], ..., a[p-1]) ) = false;
    // -1 cannot find such p
    // we want to find p <= pr, left most position which satisfied g() = true
    template<class G>
    int min_left(int p, int l, int r, int ql, int qr, G g) {
        assert(0 <= r && r <= _n);
        if (r == 0) return 0;

if (ql == l && r == qr) {
            if (!g(node[p])) return -1;
            if (l == r) return l;

int mid = (l + r) >> 1;
            push(p);
            if (g(node[p<<1])) return min_left(p<<1, l, mid, ql, mid, g);
            else return min_left(p<<1|1, mid+1, r, mid+1, qr, g);
        }

int mid = (l + r) >> 1;
        push(p);

if (qr <= mid) return min_left(p<<1, l, mid, ql, qr, g);
        else if (ql > mid) return min_left(p<<1|1, mid+1, r, ql, qr, g);
        else {
            int pos = min_left(p<<1, l, mid, ql, mid, g);
            if (pos != -1) return pos;
            else return min_left(p<<1|1, mid+1, r, mid+1, qr, g);
        }
    }
};

}

using namespace Seg;
```

看完文章有啥想法

算法小站

wiki 主题

数据结构

线段树区间修改

目录