树状数组与线段树

zifuneko · 2024-05-12 18:23:34 · 算法·理论

\text{1 树状数组}

\text{1.1 前言}

上图是一个普通的树，我们定义 t[x] 是以 x 为结尾的一段区间的和。可以看出，有一些节点是永远也不会用到的（即标黄部分），将这部分删去后，可以发现正好组成了一个数组。

\text{1.2 正文}

定义一个树， t[x] 保存以 x 为根的子树中的叶节点值的和。将每个节点用二进制表达出来。

我们会发现每一层的末尾的零的个数都是相同的。

\text{1.2.1 使用 lowbit}

在这里我们可以使用函数\operatorname{lowbit}() 。\operatorname{lowbit}(x) 的值是 x 的二进制表达式中最低位的 1 所对应的值。

则下标为 x 的节点所覆盖的区间长度为 \operatorname{lowbit}(x)。

怎么求 \operatorname{lowbit}() 的值呢？

lowbit(x) = x & (-x)

\text{1.2.2 树状数组的子节点与父节点}

通过观察节点的二进制数，进一步发现，树状数组中节点 x 的父节点的下标为 x+\operatorname{lowbit}(x) ；节点 x 的子节点的下标为 x - 2^0 , x-2^1 , ... , x-\operatorname{lowbit}(x) /2

例如：t[2] 的父节点为 t[4] = t[2+\operatorname{lowbit}(2)]

\text{1.2.3 单点修改}

在单点修改的同时，更新父节点就变得尤为简单，例如我们对 a[1]+k ，那么祖先节点 t[1] , t[2] , t[4] , t[8] 都需要 +k 更新(因为 t[] 表示前缀和)，此时我们就可以用 \operatorname{lowbit} 递归操作实现.

void add(int id, int k)
{
    while(id <= n)
    {
        t[id] += k;
        id += lowbit(id);
    }
    return;
}

\text{1.2.4 区间查询}

通过图中不难看出，sum[7]=t[7]+t[6]+t[4] ，我们进一步发现, 6=7-lowbit(7) ， 4=6-lowbit(6)，所以我们可以通过不断的 -\operatorname{lowbit} 操作来实现求和.

int ask(int id)
{
    int ans = 0;
    while(id > 0)
    {
        ans += t[id];
        id -= lowbit(id);
    }
    return ans;
}

但是这只能求区间 [1,x] 的区间和，那么如何求 [L, R] 的区间和呢？这时候利用前缀和相减的性质就可以了， [L,R] = [1,R]-[1,L-1].

模板题：\text{P3374} 【模板】树状数组 1

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 5e5+5;
int a[MAX], t[MAX], n, m;

int lowbit(int x) {return x & (-x);}
void add(int id, int v) {while(id <= n) {t[id] += v; id += lowbit(id);} return;}
int sum(int id)
{
    int ans = 0;
    while(id > 0) {ans += t[id]; id -= lowbit(id);}
    return ans;
}
int sum(int x, int y) {return sum(y) - sum(x-1);} // 多态

int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) {cin >> a[i]; add(i, a[i]);}

    for(int i=0;i<m;i++)
    {
        int opt, x, y;
        cin >> opt >> x >> y;
        if(opt == 1) add(x, y);
        else if(opt == 2) cout << sum(x, y) << endl;
    }
    return 0;
}

\text{1.2.5 区间修改，单点查询}

对于这一类操作，我们需要构造出原数组的差分数组 b ，然后用树状数组维护 b 数组即可.

对于区间修改的话，我们只需要对差分数组进行操作即可，例如对区间 [L,R]+k ,那么我们只需要更新差分数组 add(L,k) ,add(R+1,-k)，这是差分数组的性质.

模板题：\text{P3368} 【模板】树状数组 2

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int MAX = 5e5+5;
int a[MAX], cf[MAX], t[MAX], n, m;

int lowbit(int x) {return x & (-x);}
void add(int id, int v) {while(id <= n) {t[id] += v; id += lowbit(id);} return;}
int sum(int id)
{
    int ans = 0;
    while(id > 0) {ans += t[id]; id -= lowbit(id);}
    return ans;
}
int sum(int x, int y) {return sum(y) - sum(x-1);}

int main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++)
    {
        cin >> a[i];
        cf[i] = a[i] - a[i-1];
        add(i, cf[i]);
    }

    for(int i=0; i<m; i++)
    {
        int o, x, y, k;
        cin >> o;
        if(o == 1) {cin >> x >> y >> k; add(x, k); add(y+1, -k);}
        else if(o == 2) {cin >> x; cout << sum(x) << endl;}
    }
    return 0;
}

\text{1.2.6 区间修改，区间查询}

这一类操作使用树状数组就显得及其复杂，这时候建议使用扩展性更强的线段树来解决。

\text{1.2.7 权值树状数组}

计数排序， cnt[i] 代表数字 i 出现的个数
求区间和得知 \le i 的树有几个；
即可通过二分查找的方式全局第 k 小，时间复杂度为 O(\log^2n) ；
使用树状数组代替普通数组。

\text{2 线段树}

\text{2.1 前言}

线段树是一种平衡二叉查找树。

\text{2.1.1 线段树的结构}

\text{2.2 性质}

\text{2.2.1 线段树的性质}

线段树存储数据 [a,b] ，则有 b-a+1 个叶子节点
线段树的高度：k = ⌈\log_2 n⌉ + 1 ( n 为数据个数，即叶子结点个数）
线段树上没有度为 1 的节点
线段树的节点个数：2n + 1 个节点
因为存储方式是一维数组（完全二叉树），所以需要 4n - 1 的空间

\text{2.2.2 线段树的灵魂:}\operatorname{Lazy\ tag}

根据 $\operatorname{Lazy}$ 思想，我们可以在不代表原线段的结点上增加一个值 $tag$ ，即为对这个结点，留待以后执行的插入操作 $k$ 值的总和。对整个结点插入时，只更新 $sum$ 和 $tag$ 值而不向下进行，这样时间复杂度可证明为$O(\log n)$ 。等到时候查询的时候再向下放 $tag$ （就像干工作的时候等到老板视察的时候再开始工作）。对一个 $tag$ 值为 $0$ 的结点整个进行查询时，直接返回存储在其中的 $sum$ 值；而若对 $tag$ 不为 $0$ 的一部分进行查询，则要更新其左右子结点的 $sum$ 值，然后把 $tag$ 值传递下去，再对这个查询本身，左右子结点分别递归下去。（下放操作）特别的，叶子就不需要拥有 $tag$ 的值。在线段树中，需要特别注意叶子结点的判断。区间修改与区间查询一样找到被包含区间，然后直接统计区间信息，并把需要下传的修改信息记录，等被查询时再向下传递。【经验】： 1. 多个修改到结点时，如何记录最终修改的结果（Lazy）； 2. 如何用修改值去更新区间信息； 3. Lazy 的初始值。 ## $\text{2.3 区间修改，区间查询}

\text{P3372} 【模板】线段树 1

\text{2.3.1 MakeTag}

```cpp if(tree[u].l < tree[u].r) tree[u].tag += x; tree[u].val += (tree[u].r - tree[u].l + 1) * x; ``` ### $\text{2.3.2 PushDown}

当要下传标记时，需要使用 \text{PushDown} 函数：如若没有 tag ，那么无需下传标记，如果有，那么将左孩子和右孩子都分别打上标记（下传），最后将标记设为初始值，代表下传完毕。

if(tree[u].tag == 0) return;
maketag(lson(u), tree[u].tag);
maketag(rson(u), tree[u].tag);
tree[u].tag = 0;

\text{2.3.3 完整代码}

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int MAX = 1e5+5;
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)
#define mid ((l + r) >> 1)

int n, m, val[MAX];
struct Segment_tree
{
    int l, r;
    long long val, tag;
} tree[MAX << 2];

inline bool out(int u, int l, int r) {if(tree[u].l > r || tree[u].r < l) return 1; return 0;}
inline bool in(int u, int l, int r) {if(tree[u].l >= l && tree[u].r <= r) return 1; return 0;}

inline void pushup(int u)
{
    if(tree[u].l == tree[u].r) return;
    tree[u].val = tree[lson(u)].val + tree[rson(u)].val;
}

inline void maketag(int u, int x)
{
    if(tree[u].l < tree[u].r) tree[u].tag += x;
    tree[u].val += (tree[u].r - tree[u].l + 1) * x;
}

inline void pushdown(int u)
{
    if(tree[u].tag == 0) return;
    maketag(lson(u), tree[u].tag);
    maketag(rson(u), tree[u].tag);
    tree[u].tag = 0;
}

long long query(int u, int l, int r)
{
    if(out(u, l ,r)) return 0;
    if(in(u, l ,r)) return tree[u].val;
    pushdown(u);
    return query(lson(u), l, r) + query(rson(u), l, r);
}

void modify(int u, int l, int r, int x)
{
    if(out(u, l, r)) return;
    if(in(u, l, r)) maketag(u, x);
    else
    {
        pushdown(u);
        modify(lson(u), l, r, x);
        modify(rson(u), l, r, x);
        pushup(u);
    }
}

void build(int u, int l, int r)
{
    tree[u].l = l;
    tree[u].r = r;
    if(l == r) {tree[u].val = val[l]; return;}

    build(lson(u), l, mid);
    build(rson(u), mid+1, r);
    pushup(u);
}

signed main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> val[i];
    build(1, 1, n);

    while(m--)
    {
        int x, y, op, k;
        cin >> op;
        if(op == 1) {cin >> x >> y >> k; modify(1, x, y, k);}
        else {cin >> x >> y; cout << query(1, x, y) << endl;}
    }

    return 0;
}

\text{2.4 区间加法，区间乘法，区间查询}

\text{P3373} 【模板】线段树 2：区间加法，区间乘法，区间查询。在 \text{P3372} 【模板】线段树 1 的基础上，多维护一个 \text{Lazy tag} 即可实现。

\text{2.4.1 具体方法}

具体的，区间加法和之前一致，而在区间乘法就有些不同了。在下传标记时，需要维护两个标记，一个是加法标记 \text{add}，还有一个是乘法标记 \text{mul}：

$\text{val}$: 因为 $\text{add}$ 之前已经乘过，所以在子孩子乘过 $\text{times}$ 后直接加就行。 $\text{mul}$: 直接乘上父亲的 $\text{times}$ 即可。 ```cpp tree[u].val = (tree[u].val * times + (tree[u].r - tree[u].l + 1) * plus) % MOD; tree[u].mul = (tree[u].mul * times) % MOD; tree[u].add = (tree[u].add * times + plus) % MOD; ``` ### $\text{2.4.2 含义}

上面的变量名含义分别为：	名称	含义
\text{val}	当前节点的值
\text{add}	子节点的加法标记
\text{plus}	父节点下传来的加法标记
\text{mul}	子节点的乘法标记
\text{times}	父节点下传来的乘法标记

\text{2.4.3 注意事项}

特别的要注意，乘法标记的初始值需要设置为 1。

\text{2.4.4 完整代码}

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 1e5+5;
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)
#define mid ((l + r) >> 1)

int n, q, MOD, val[MAX];
struct Segment_tree
{
    int l, r;
    long long val, add, mul;
}
tree[MAX << 2];

inline bool out(int u, int l, int r) {if(tree[u].l > r || tree[u].r < l) return 1; return 0;}
inline bool in(int u, int l, int r) {if(tree[u].l >= l && tree[u].r <= r) return 1; return 0;}

inline void pushup(int u)
{
    if(tree[u].l == tree[u].r) return;
    tree[u].val = tree[lson(u)].val + tree[rson(u)].val;
}

inline void maketag(int u, int ad, int ti)
{
    tree[u].val = (tree[u].val * ti + (tree[u].r - tree[u].l + 1) * ad) % MOD;
    if(tree[u].l < tree[u].r)
    {
        tree[u].mul = (tree[u].mul * ti) % MOD;
        tree[u].add = (tree[u].add * ti + ad) % MOD;
    }
}

inline void pushdown(int u)
{
    if(tree[u].add == 0 && tree[u].mul == 1) return;
    maketag(lson(u), tree[u].add, tree[u].mul);
    maketag(rson(u), tree[u].add, tree[u].mul);
    tree[u].add = 0; tree[u].mul = 1;
}

long long query(int u, int l, int r)
{
    if(out(u, l ,r)) return 0;
    if(in(u, l ,r)) return tree[u].val;
    pushdown(u);
    return (query(lson(u), l, r) + query(rson(u), l, r)) % MOD;
}

void modify(int u, int l, int r, int x, int op)
{
    if(out(u, l, r)) return;
    if(in(u, l, r))
    {
        if(op == 1) maketag(u, 0, x);
        else maketag(u, x, 1);
    }
    else
    {
        pushdown(u);
        modify(lson(u), l, r, x, op);
        modify(rson(u), l, r, x, op);
        pushup(u);
    }
}

void build(int u, int l, int r)
{
    tree[u].l = l;
    tree[u].r = r;
    tree[u].mul = 1;
    if(l == r) {tree[u].val = val[l] % MOD; return;}

    build(lson(u), l, mid);
    build(rson(u), mid+1, r);
    pushup(u);
}

signed main()
{
    cin >> n >> q >> MOD;
    for(int i=1; i<=n; i++) cin >> val[i];
    build(1, 1, n);

    while(q--)
    {
        int x, y, op, k;
        cin >> op;
        if(op == 1 || op == 2) {cin >> x >> y >> k; modify(1, x, y, k%MOD, op);}
        else {cin >> x >> y; cout << query(1, x, y) << endl;}
    }

    return 0;
}

\text{2.5 线段树维护最大子段和}

\text{P4513} 小白逛公园

\text{2.5.1 变量含义}

名称	含义
\text{max}	最大连续字段和
\text{lmax}	从区间左端点开始的连续子序列的最大和
\text{rmax}	从区间右端点开始的连续子序列的最大和
\text{sum}	[l, r] 中所有节点和

\text{2.5.2 PushUp}

\text{2.5.3 完整代码}

其余的在注释中写的比较完善。

#include<bits/stdc++.h>
using namespace std;

const int MAX = 5e5+5;
#define lson(x) (x << 1)
#define rson(x) (x << 1 | 1)
#define mid ((l + r) >> 1)

int n, m, a[MAX];
struct Node{int l, r; long long max, lmax, rmax, sum;}
tree[MAX << 2];

bool out(int u, int l, int r) {if(tree[u].l > r || tree[u].r < l) return 1; return 0;} // 判断节点u是否完全在查询区间[l,r]之外
bool in(int u, int l, int r) {if(tree[u].l >= l && tree[u].r <= r) return 1; return 0;} // 判断节点u是否完全包含在查询区间[l,r]内

/*
max 最大连续字段和
lmax 从区间左端点开始的连续子序列的最大和
ramx 从区间右端点开始的连续子序列的最大和
sum [l, r]中所有节点和

区间最大子段和可能是：左子区间的最大子段和；右子区间的最大子段和；左子区间的右最大+右子区间的左最大
tree[u].max = max({tree[lson].max, tree[rson].max, tree[lson].rmax + tree[rson].lmax});
从左开始的最大子段和可能是：左子区间的从左最大；左子区间的总和+右子区间的从左最大
tree[u].lmax = max(tree[lson].lmax, tree[lson].sum + tree[rson].lmax);
从右开始的最大子段和可能是：右子区间的从右最大；右子区间的总和+左子区间的从右最大
tree[x].rmax = max(tree[rson].rmax, tree[rson].sum + tree[lson].rmax);
*/
void pushup(Node& root, Node l, Node r)
{
    root.sum = l.sum + r.sum;
    root.max = max({l.max, r.max, l.rmax + r.lmax});
    root.lmax = max(l.lmax, l.sum + r.lmax);
    root.rmax = max(r.rmax, r.sum + l.rmax);
}

Node ask(int u, int l, int r)
{
    if (in(u, l, r)) return tree[u];
    if (out(u, l, r)) return Node();
    if (tree[lson(u)].r >= l && tree[lson(u)].r < r) // 如果查询区间跨越了左右子节点
    {
        Node res;
        pushup(res, ask(lson(u), l, r), ask(rson(u), l, r)); // 合并信息
        return res;
    }
    else if (tree[lson(u)].r>=r) return ask(lson(u), l, r); // 查询区间完全在左子节点
    else return ask(rson(u), l, r); // 查询区间完全在右子节点
}

void update(int u, int p, int s)
{
    // 找到目标叶子节点
    if(tree[u].l == p && tree[u].r == p) {tree[u].sum = tree[u].max = tree[u].lmax = tree[u].rmax = a[p] = s; return;}
    if(out(u, p, p)) return; // 不在当前节点区间内
    // 递归更新子节点
    if(tree[lson(u)].r >= p) update(lson(u), p, s);
    if(tree[rson(u)].l <= p) update(rson(u), p, s);
    // 更新当前节点信息
    pushup(tree[u], tree[lson(u)], tree[rson(u)]);
}

void build(int u, int l, int r)
{
    tree[u].l = l;
    tree[u].r = r;
    if(l == r) {tree[u].sum = tree[u].max = tree[u].lmax = tree[u].rmax = a[l]; return;} // 叶子
    build(lson(u), l, mid);
    build(rson(u), mid+1, r);
    pushup(tree[u], tree[u << 1], tree[u << 1 | 1]);
}

signed main()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    build(1, 1, n);

    for(int i=1; i<=m; i++)
    {
        int opt, a, b, p, s;
        cin >> opt;
        if(opt == 1)
        {
            cin >> a >> b; if(a > b) swap(a, b);
            cout << ask(1, a, b).max << endl;
        }
        else if(opt == 2) {cin >> p >> s; update(1, p, s);}
    }

    return 0;
}

\text{2.6 线段树动态开点技巧}

\text{2.6.1 运用场景}

运用场景：

线段树要维护 [1, 10^9] 的区间信息，但是查询和修改的次数最多是 10^6.
线段树对维护实数区间，比如 [1.11,1.56].

解决方法：

离散化（最优，但是细节会比较多）
动态开点线段树（空间相较于离散化会用的更多）

\text{2.6.2 核心与易错点}

\text{P1168} 中位数

P13825 【模板】线段树 1.5

动态开点的核心：

inline int ls(int u) {return(tree[u].l != 0 ? tree[u].l : tree[u].l = ++cnt);}
inline int rs(int u) {return(tree[u].r != 0 ? tree[u].r : tree[u].r = ++cnt);}

动态开点不需要使用 \text{build} 函数。在本篇代码中，变量 \text{cnt} 需要定义在全局。

\text{2.6.3 完整代码}

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAX = 1e7+5;
const int LIM = 1e9;
#define mid ((l + r) >> 1)

int n, op, x, y, cnt=1;
struct Seg_tree {int num, l, r;} tree[MAX];
inline int ls(int u) {return(tree[u].l != 0 ? tree[u].l : tree[u].l = ++cnt);}
inline int rs(int u) {return(tree[u].r != 0 ? tree[u].r : tree[u].r = ++cnt);}
void pushup(int u) {tree[u].num = tree[ls(u)].num + tree[rs(u)].num;}

int query(int u, int l, int r, int ranked)
{
    if(l == r) return r;
    if(tree[ls(u)].num >= ranked) return query(ls(u), l, mid, ranked);
    else return query(rs(u), mid+1, r, ranked - tree[ls(u)].num);
}

void modify(int u, int l, int r, int pos)
{
    if(l == r) {tree[u].num += 1; return;}
    if(pos <= mid) modify(ls(u), l, mid, pos);
    if(mid < pos) modify(rs(u), mid+1, r, pos);
    pushup(u);
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    for(int i = 1; i<=n; i++)
    {
       cin >> x; modify(1, 1, LIM, x);
       if(i % 2 == 1) cout << query(1, 1, LIM, (i+1)/2) << endl;
    }
    return 0;
}

\text{3 总结}

树状数组：满足结合律和可差分时可以使用，比线段树快；

线段树：只要满足结合律都可以使用。

5/12/2024 的代码：https://www.luogu.com.cn/paste/qqrpxbev