树状数组

应用场景

1) 统计相对关系的数量, 对于无法直接用值作为数组下标的可以离散化(将数组排序, 转化为相对关系, 相当于将其转化为排名), 将数作为下标在树状数组对应位置加一, 就可以利用sum来统计数量了,
例如: 有多少个点小于当前点之类的, 或者进一步有多少个点大于当前点的两倍等;
2) 差分, 对比普通差分, 优势为: 在查询某个数的时候时间是O(logn);

树状数组实现模板(之后省略)

原理可参考

https://www.acwing.com/file_system/file/content/whole/index/content/6603080/

#include <iostream>
using namespace std;
const int N = 100010;

int n, a[N], tr[N], ans[N];

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

void add(int x, int d)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += d;
}

int sum(int x)
{
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

应用场景1

788. 逆序对的数量

思路

1) 将数组离散化处理, 处理为相对关系, 并且去重;
2) 利用在相应位置标记1, 表示这个数已经存在;
3) sum(m) - sum(x), 代表前面有都个x + 1 ~ m范围的数, 即前面大于x的数的个数;

C++代码

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++) 
    {
        scanf("%d", &a[i]);
        b[i] = a[i];
    }
    //去重
    sort(b, b + n);
    unordered_map<int, int> mp;
    for (int i = 0; i < n; i ++)
        if (!i || b[m - 1] != b[i]) mp[b[i]] = ++ m;
        // 哈希会耗掉大量空间, 代替的可以使用二分在b中查找得到相应a的下标

    long long ans = 0;
    for (int i = 0; i < n; i ++)
    {
        int x = mp[a[i]];
        ans += sum(m) - sum(x);
        add(x);// 都是加一, 不用多传一个参了
    }
    cout << ans;
}

AcWing 241. 楼兰图腾

思路

利用树状数组
由于范围在1~n之内, 将y坐标为下标, 每次加一;
随着sum(n) - sum(y) 即前面有多少个点y坐标在y + 1 ~ n范围内, 也就是有多少个点大于y;
同理sum(y - 1) 即有多少个点小于y;

C++代码

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);

    for (int i = 1; i <= n; i ++)// 从前往后有多少个
    {
        int y = a[i];
        g[i] = sum(n) - sum(y);
        l[i] = sum(y - 1);
        add(y, 1);
    }

    memset(tr, 0, sizeof tr);
    LL res1 = 0, res2 = 0;
    for (int i = n; i; i --)
    {
        int y = a[i];
        res1 += g[i] * (LL)(sum(n) - sum(y));
        res2 += l[i] * (LL)sum(y - 1);
        add(y, 1);
    }

    printf("%lld %lld", res1, res2);
}

244. 谜一样的牛

思路

1) 从后往前看, a[i]就代表了在还未被占用的排名中排第a[i]位
2) 未被使用的排名被赋值为1, 其前缀和代表前面未被使用的排名个数;(跟前面相同, “未被使用”就是”还存在”的意思嘛)
3) 选取未被使用的排名的第k个就是 和(sum(x)) 从k - 1 -> k突变的那个位置, 查找可以用二分法确定;

C++代码

int main()
{
    scanf("%d", &n);
    for (int i = 2; i <= n; i ++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++) tr[i] = lowbit(i);
    for (int i = n; i; i --)
    {
        int l = 0, r = n, k = a[i] + 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (sum(mid) >= k) r = mid;
            else l = mid + 1;
        }
        ans[i] = l;
        add(l, -1);
    }
    for (int i = 1; i <= n; i ++) printf("%d\n", ans[i]);
}

应用场景2

242. 一个简单的整数问题

思路

用差分去建立树状数组, 这样就可以把查询和插入都控制在O(logn)内了.
普通数组插入是O(1), 查询是O(n).

C++代码

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++) add(i, a[i] - a[i - 1]);

    while (m --)
    {
        // cout << m << endl;
        char op[2];
        int l;
        scanf("%s%d", op, &l);
        if (*op == 'C')
        {
            int r, d;
            scanf("%d%d", &r, &d);
            add(l, d), add(r + 1, -d);
        }
        else 
        {
            printf("%d\n", sum(l));
        }
    }
}

243. 一个简单的整数问题2

思路

C++代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;

int n, m;
int a[N];
LL tr1[N];  // 维护b[i]的前缀和
LL tr2[N];  // 维护b[i] * i的前缀和

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

void add(LL tr[], int x, LL c)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

LL sum(LL tr[], int x)
{
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

LL prefix_sum(int x)
{
    return sum(tr1, x) * (x + 1) - sum(tr2, x);
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &a[i]);
    for (int i = 1; i <= n; i ++ )
    {
        int b = a[i] - a[i - 1];
        add(tr1, i, b);
        add(tr2, i, (LL)b * i);
    }

    while (m -- )
    {
        char op[2];
        int l, r, d;
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'Q')
        {
            printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
        }
        else
        {
            scanf("%d", &d);
            // a[l] += d
            add(tr1, l, d), add(tr2, l, l * d);
            // a[r + 1] -= d
            add(tr1, r + 1, -d), add(tr2, r + 1, (r + 1) * -d);
        }
    }
}
//作者：yxc