算法提高课：树状数组扩展 +差分、+公式

101 阅读 0 评论 67 点赞

我是靠谱客的博主孝顺豆芽，这篇文章主要介绍算法提高课：树状数组扩展 +差分、+公式，现在分享给大家，希望可以做个参考。

基本原理

应用:
快速求前缀和
修改某一个数
在这里插入图片描述
分成最多logx个部分，算1-x总和的时候，在加logn个数就可以求出来，复杂度O(logn)
2 ^ i1 是x的二进制表示的最后一位1

c[x]表示以x为右端点，长度lowbit的区间内所有数的和

在这里插入图片描述
图中C12应为C9-C12.

所有C的关系如图：
在这里插入图片描述
x> 0, 必然存在最后一位1
x = ----- 100…0， 0 y有k个
Cx = 以x结尾，长度为2^k的区间和
找到x的所有子节点
x-1每一次去掉一个最后的1，去地道k次、
如何通过子节点找父节点

树状数组的建立方式，关于优化时间负责度的（不是很明白）

扩展 +差分、+公式

在这里插入图片描述
参考差分

令b[n]为a[n]的差分数组，将[L, R] +c 等价于b[l] += c, b[r + 1] -= c;

例题

楼兰图腾

将V最下面那个点的横坐标分成n类
在这里插入图片描述
对于yk，统计有多少处于1——k-1、有多少大于yk，处于k+1 —— n的大于yk，相乘
greater[k].
与之对应的lower[k]，表示的是小于yk的相乘

一个简单的整数问题

维护差分数组

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 100010;
typedef long long LL;

int a[N], m, n, l, r, d;
LL tr[N];
char op[2];
int lowbit(int x)
{
   
    return x & -x;
}

void update(int x, int c)  // 位置x加c
{
   
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

LL query(int x)  // 返回前x个数的和
{
   
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

int main()
{
   
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
    {
   
        cin >> a[i];
    }
    for (int i = 1; i <= n; i ++ )
    {
   
        update(i, a[i] - a[i - 1]);//把a数组转化成差分数组
    }
    while (m -- )