–2022.2.18更新树状数组维护区间最值

树状数组维护区间和/最值

假设给定我们一个数组，让我们进行单点修改和区间查询操作，则需要O（1）和O（n）的时间复杂度，多次修改查询的总复杂度最坏为O（n^2），而用树状数组进行这些操作的时间复杂度仅有O（logn），总最坏时间复杂度为O（nlogn）。

引入-lowbit操作

lowbit（x）非负整数x在二进制表示下最低位1及其后面的0构成的数值。

例如

lowbit(44) = lowbit(101100) = (100) = 4;

一个数x(101100)将其取反后(010011)在加一(010100)后，我们可以观察到，在二进制上除最低位1及其后面的0，其余所有位都取反了，此时我们再与原数进行按位与操作，就能得到x的lowbit。

计算机在存储时用的是补码而非反码，因此在编译器中的-x表示的就是x取反后加一，因此：

lowbit(X) = x & -x;

树状数组维护区间和

我们在一个数组a上建立以上的树形结构，每个节点t[x]保存以x为根的子树中叶结点值的和。

t[x]节点覆盖的长度即为lowbit(x)。

t[x]节点的父节点为t[x + lowbit(x)]。

单点修改操作 & 建立树状数组

可见，我们修改一个点，也要修改其上的父节点，最坏的时间复杂度为O(logn)

void add(int x, int k){
	for (; x <= n; x += x & -x) t[x] += k;
}

如何建立树状数组？

有了单点修改的操作，我们只需要在读入时对每个t[i]进行add操作即可

for (int i = 1; i <= n; i ++ ){
	int x;
	cin >> x;
	add(i, a);
}

区间查询操作

而对于区间查询（以7为例），我们要同时加上t[7], t[6],t[4]（即覆盖了a[1]~a[7]的所有t[x])。

int ask(int x){
	int ans = 0;
	for (; x; x -= x & -x) ans += t[x];
	return ans;
}

//单点修改与区间查询
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, p;
int q[1123456], t[1123456];

inline int lowbit(int x)
{
    return x & -x;
}

void add(int x, int k)
{
    for (; x <= n; x += lowbit(x)) t[x] += k;
}

int ask(int x)
{
    int ans = 0;
    for (; x; x -= lowbit(x)) ans += t[x];
    return ans;
}

signed main()
{
    cin >> n >> p;
    for (int i = 1; i <= n; i ++ ){
        cin >> q[i];
        add(i, q[i]);
    }
    
    while (p -- ){
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1) add(x, y);
        if (op == 2) cout << ask(y) - ask(x - 1) << endl;
    }

    return 0;
}

区间修改与单点查询

要将一个区间内同时加上一个数k，或查询当前的第i个数，我们需要新的操作。

注意初始化树状数组时b[i] = q[i] - q[i - 1];

//区间修改与单点查询
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, p;
int q[1123456], t[1123456];

inline int lowbit(int x)
{
    return x & -x;
}

void add(int x, int k)
{
    for (; x <= n; x += lowbit(x)) t[x] += k;
}

int ask(int x)
{
    int ans = 0;
    for (; x; x -= lowbit(x)) ans += t[x];
    return ans;
}

signed main()
{
    cin >> n >> p;
    for (int i = 1; i <= n; i ++ ){
        cin >> q[i];
        add(i, q[i] - q[i - 1]);
    }
    
    while (p -- ){
        int op, l, r, x;
        cin >> op;
        if (op == 1){
            cin >> l >> r >> x;
            add(l, x), add(r + 1, -x);
        }
        if (op == 2){
            cin >> x;
            cout << ask(x) << endl;
        }
    }

    return 0;
}

区间修改与区间查询

如图，我们仍用树状数组维护差分数组b的前缀和，区间查询的值即为蓝色部分，我们可以发现蓝色部分不方便计算，因此构建一个大矩形（红色），再减去不计算的部分（黄色），这一部分我们可以维护另外一个i*b[i]的前缀和数组。

//区间修改与区间查询
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, p;
int q[1123456], t[1123456], s[1123456], sum[1123456];

inline int lowbit(int x)
{
    return x & -x;
}

void add1(int x, int k)
{
    for (int i = x; i <= n; i += lowbit(i)) t[i] += k, s[i] += x * k;
}

int ask1(int x)
{
    int ans = 0;
    for (int i = x; i; i -= lowbit(i)) ans += (x + 1) * t[i] - s[i];
    return ans;
}

signed main()
{
    cin >> n >> p;
    for (int i = 1; i <= n; i ++ ){
        cin >> q[i];
        sum[i] = q[i] + sum[i - 1];
        add1(i, q[i] - q[i - 1]);
    }
    
    while (p -- ){
        int op, l, r, x;
        cin >> op;
        if (op == 1){
            cin >> l >> r >> x;
            add1(l, x), add1(r + 1, -x);
        }
        if (op == 2){
            cin >> l >> r;
            cout << ask1(r) - ask1(l - 1) << endl;
        }
    }

    return 0;
}

本篇题解图片来自〔manim | 算法 | 数据结构〕 完全理解并深入应用树状数组 | 支持多种动态维护区间操作 个人认为讲的很详细。

树状数组维护最大值

用树状数组维护最大值。同样可以让每个节点t[x]保存以x为根的子树中叶结点值的最大值，对于维护的最大值，我们同样可以进行单点修改和区间查询操作。

单点修改

由之前维护区间和的单点修改操作，我们很容易想到：

void add(int x, int k){ // 将q[x]变为k
	for (; x <= n; x += lowbit(x)) t[x] = max(t[x], k);
}

这段代码是由前面树状数组维护区间和里单点操作修改而成，仅将t[x]+=k 变为 t[x] = max(t[x], k)。

那么这段代码是否可行呢？

如果我们要将这个数变大，即k >= q[x]，那么这段代码是没有问题的，t[x]每次都会更新，然后往上一步步寻找。但想一下，如果k < q[x]，并且q[x]恰好是t[x]覆盖范围内唯一的最大值，那么我们要将q[x]变小，其范围内最大值，即t[x]也一定会变小，但这个max操作并不会将t[x]变小，因此这样的单点修改是不可行的。

唯一的方法，是连同q[x]和t[x]一起更新，不进行max操作，然后往上找相关的数继续更新。

还是该图，我们想一下，与t[8]直接相关的有几个数？

很容易观察到：

t[8] = max({a[8], t[4], t[6], t[7]});

我们转化为二进制观察：

t[1000] = max({a[1000], t[100], t[110], t[111]});

这里我们直接给出公式：

t[i] = max({q[i], t[i - lowbit(i)/(2^1)], t[i - lowbit[i]/(2^2)]...t[i - 2^0]});

代码：

void update(int x, int k){ // 将q[x]变为k
    q[x] = k; // 将原数组也改变，可加可不加
	for (; x <= n; x += lowbit(x)){
		t[x] = k; // 直接更新
		for (int i = 1; i < lowbit(x); i <<= 1) t[x] = max(t[x], t[x - i]);//公式
	}
}

区间查询

查询区间[l, r]的最大值，需要用上原数组。

区间查询的过程我们主要用分类讨论解决。

如果 r - lowbit(r) + 1 >= l, ans = max(query(l, r - lowbit(r)), t[r]);

否则 res = max(query(l, r - 1), q[r]);

直接看代码吧，不难理解：

int query(int l, int r)
{
	int ans = 0;
    while (r >= l){
		ans = max(q[r], ans), r -- ;
        for (; r - lowbit(r) >= l; r -= lowbit(r)) ans = max(t[r], ans);
    }
    return ans;
}

尾部添数

树状数组维护最大值支持向区间尾部添加一个值。

void add(int x)
{
	q[ ++ tot] = x;
    t[tot] = max(q[tot], query(tot + 1 - lowbit(tot), tot - 1));
}