wiki - 算法小站

wiki 主题

主题名称

是否为父主题

是否为其添加wiki文章

选择主题

修改主题名称

修改父主题

修改wiki文章

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

数据结构

线段树

线段树单点修改

线段树区间修改

可持久化线段树

树链剖分

平衡树

FHQ-Treap

[[ item.c ]]

线段树单点修改

线段树在很多情况下，可以看作是在**单群**上建立的数据结构，单群需要满足的性质有
* 
	
	$$ a, b, c \in S $$，有**结合律**成立，$$ (a \cdot b) \cdot c = a \cdot (b \cdot c) $$

*   存在**幺元** $$e$$，对于所有 $$a \in S$$，有 $$a \cdot e = e \cdot a = a$$

## 线段树的单点修改
### 构造函数和相关方法

```bash
segTree<S, op, e> seg(int n)
segTree<S, op, e> seg(vector<S> v)
```
* `S` 是元素的类型，比如根据 `vector<long long> a` 来建立一棵线段树
  那么应该这样初始化声明 `segTree<long long, op, e> seg`
  
* `op` 对应线段树节点 `pull` 方法，`S op(S a, S b)`

下面以**求区间的最小值**为例
	```bash
	int op(int a, int b) {
		return min(a, b);
	}
	```
* `e` 为**幺元**或者说是**单位元**，`S e()`，同样以区间最小值为例
	```bash
	int e() {
		return (int)(1e9)
	}
	```
	这是因为对于任意一个节点值 `x`，我们有 `op(x, e())`（仍以最小值为例）
	`min(x, e()) = x`，符合幺元性质
	
### 单点修改和查询

**set, get**
**单点修改** `void seg.set(int p, S x)`
执行 `a[p] = x` 操作，复杂度为 $$O(\log n)$$

**单点查询** `S seg.get(int p)`，返回 `a[p]` 的值

### 区间查询
**prod**

`S seg.prod(int l, int r)`
对应线段树的**区间查询**，注意是 $$[l, r)$$ 的查询结果
返回 `op(a[l], a[l+1], ..., a[r-1])` 的值
这里的 `op` 可以是区间加，也可以是区间乘，区间矩阵运算，或者最大值，最小值，`gcd` 等等

特别地，如果 `l = r`，我们返回**幺元** `e()`，复杂度是 $$O(\log n)$$

**all_prod**

`S seg.all_prod()`
返回 `op(a[0], ..., a[n-1])`，特别地，如果 `n = 0`，返回 `e()`

注意到，我们用线段树解决问题的时候，经常取序列下标 $$[1, n]$$
这个时候我们只需要让 `a[0] = e()` 即可

复杂度是 $$O(1)$$

### 线段树二分
#### max_right
注意线段树二分算法处理的区间一般都是 $$[l, r)$$，**左闭右开**
```
(1) int seg.max_right<f>(int l)
(2) int seg.max_right<F>(int l, F f)
```

给定操作 `(l, r, d)`，查询 $$a\_l, a\_{l+1}, \cdots, a\_r$$ 中
**第一个满足** $$\geq d$$ 的数的下标

其中 `f` 是一个函数对象，必须定义
```bash
bool f(S x)
// 特别地，f(e()) = true
```

函数的返回值是 `r`，是**第一个不符合** `f` 条件的下标

* `f( op(a[l], a[l+1], ..., a[r-1]) ) = true`，但是
  `f( op(a[l], a[l+1], ..., a[r-1], a[r]) ) = false`
  
* 如果一整段都符合，那么返回 `r = n`，如果只有一个数符合，从 `a[l+1]...` 开始都不符合，那么返回 `r = l`

* 举个例子，找到从下标 `1` 开始，最后一个满足 $$a\_1 + \cdots + a\_r < 20$$ 的位置 `r`
  ```bash
  int op(int a, int b) {
      return a + b;
  }
  int e() {
      return 0;
  }
  bool f(int x) {
      return x < 20;
  }
  // a = {1, 4, 5, 7, 10, 100}
  segTree<int, op, e> seg({1, 4, 5, 7, 10, 100})
  cout << seg.max_right<f>(1) << endl;
  // 输出 4
  ```
  程序返回 `4`，`a[4] = 10`，注意到 `a[1] + a[2] + a[3] = 16 < 20`
  但是 `16 + a[4] > 20`，所以第一个不满足的下标就是 `4`
  
  
#### min_left

```bash
(1)  int seg.min_left<f>(int r)
(2)  int seg.min_left<F>(int r, F f)
```

类似地，同样必须定义一个函数对象
```
bool f(S x)
// 特别地，f(e()) = true
```

函数的返回值是一个下标 `l`，其中

* `f( op(a[l], a[l+1], ..., a[r-1]) ) = true` 但是
  `f( op(a[l-1], a[l], ..., a[r-1]) ) = false`
  
* 如果一整段都满足，返回 `l = 0`，没有一段满足，返回 `l = r`

## 一些例子
给定一个序列，$$a_1,\cdots, a_r$$，支持以下操作

*  修改 `a[x] = d`
*  查询 `[l, r]` 的最大子段和

**算法分析**

最大子段和是一个经典问题，执行区间合并 `op` 操作的时候，最大子段和
要么只在左半边区间取到，要么只在右半边取到，或者是横跨左右两个半区间
考虑维护最大子段和 `mss`，前缀最大值 `mpre`，后缀最大值 `msuf`
设左儿子为 `l`，右儿子为 `r`

*  `mss = max(l.mss, r.mss, l.msuf + r.mpre)`，其中 `l.msuf + r.mpre` 表示子段和横跨左右两个区间
*  考虑维护`msuf, mpre`，以 `msuf` 为例子，`msuf = max(r.msuf, r.sum + l.msuf)`

简单来说，后缀最大值，要么右半区间一整段都取，再加上左半区间的后缀最大值
要么就是只取右半边的后缀最大值

实现代码如下

```bash
ll inf = 2e9;

struct S {
    ll sum, mss, mpre, msuf;
};

S op(S a, S b) {
    S res;
    res.sum = a.sum + b.sum;
    res.mpre = max(a.mpre, a.sum + b.mpre);
    res.msuf = max(b.msuf, b.sum + a.msuf);
    res.mss = max( {a.mss, b.mss, a.msuf + b.mpre} );
    return res;
}

S e() {
    return S{ 0, -inf, -inf, -inf };
}

int main() {
    vector<S> a(n, S{0, 0, 0, 0});
    for (int i = 0; i < n; i++) scanf("%lld", &a[i].sum);
    for (int i = 0; i < n; i++) {
        a[i].mss = a[i].mpre = a[i].msuf = a[i].sum;
    }

segtree<S, op, e> seg(a);

while (q--) {
        // ... 其他代码
        if (op == 1) {
            seg.set(x, S{d, d, d, d});
        }
        else {
            auto res = seg.prod(l, r+1);
        }
    }
}
```

## 线段树模版

```bash
namespace Seg {

template <class S, S (*op)(S, S), S (*e)()>
struct segtree {
public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = 4 * _n;
        node = std::vector<S>(size, e());
        to_node = std::vector<int>(_n+2, 0);

function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (l >= r) {
                node[p] = v[l];
                to_node[l] = p;
                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);
    }

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

S get(int p) const {
        assert(0 <= p && p < _n);
        return node[to_node[p]];
    }

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

// return p in [l, r], satisfy:
    // f( op(a[l], a[l+1], ..., a[p-1]) ) = true
    // f( op(a[l], a[l+1], ..., a[p]) ) = false
    // -1, we cannot find such p, in other words,
    // we want to find first position that f() = false
    template<bool (*f)(S)> int max_right(int l, int r) const {
        return max_right(1, 0, _n-1, l, r, [](S x) { return f(x); });
    }

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

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

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

// v[pos] -> x
    void change(int p, int l, int r, int pos, S x) {
        if (l >= r) {
            node[p] = x;
            return;
        }
        int mid = (l + r) >> 1;
        if (pos <= mid) change(p<<1, l, mid, pos, x);
        else change(p<<1|1, mid+1, r, pos, x);

pull(p);
    }

S query(int p, int l, int r, int ql, int qr) const {
        if (ql <= l && r <= qr) return node[p];
        int mid = (l + r) >> 1;
        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 r <= qr, satisfy:
    // f( op(a[ql], a[ql+1], ..., a[r-1]) ) = true
    // f( op(a[ql], a[ql+1], ..., a[r]) ) = false
    // -1, we cannot find such r
    // we want to find first position f() false!
    template <class F>
    int max_right(int p, int l, int r, int ql, int qr, F f) const {
        assert(0 <= l && l <= _n);
        // assert(f(e()));
        if (ql == _n) return _n;

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

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

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

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

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

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

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

}  // namespace atcoder
// segtree finished

using namespace Seg;
```

看完文章有啥想法

fogsail

支持，线段树 $$x \to f(x)$$ 很有意思 ```bash S mapping(F f, S x) { return S{}; } ``` 这种方法很新 ![](https://static.zhihu.com/heifetz/assets/kanshan.0c7f1d08.png)

2023-05-23 10:21:42
点赞（0）回复（0）
fogsail

支持支持![emoji](https://face.t.sinajs.cn/t4/appstyle/expression/ext/normal/6e/2018new_guzhang_thumb.png)![emoji](https://face.t.sinajs.cn/t4/appstyle/expression/ext/normal/6e/2018new_guzhang_thumb.png)

2023-05-23 10:19:38
点赞（0）回复（0）
fogsail

不错哦，赞一个

2023-05-23 10:19:01
点赞（1）回复（1）

fogsail @ fogsail

不错～

2023-05-23 10:19:08
点赞（0）回复（0）

算法小站

wiki 主题

数据结构

线段树单点修改

fogsail

fogsail

fogsail

fogsail @ fogsail

目录