树状数组

树状结构，用数组来模拟，开O(n)的空间即可。

一般是权值树，原数组的“值”作为树状数组的“下标”。

动态维护区间和

a = [1, 2, 3, 4, 5]

t = [....]

lowbit：lowbit(x) = x & -x;

t[i]的管辖区间:[i - lowbit(i) + 1, i]

单点修改 向右走

复杂度O(logn)

add(int k, int x);

1.找到点k所在的所有区间，+lowbit找到父亲（父亲的管辖区间一定比自己的大，且包含自身）

2.给所有途经的区间加上x

3.修改的值，和途经节点无关，只和初始节点有关

区间查询 向左走

复杂度O(logn)

int getsum(int k);

1.找到点k所在的最右边的区间，t[k]，然后往左走，直到走不动了

2.把沿途的节点的值全部加起来

区间修改

前面全部都是修改，后面全部都是查询的话：前缀和+差分

维护的就是两个差分数组diff。

d1[]维护di，d2维护di * (i - 1)。

修改的值，和途经节点无关，只和初始节点有关。

例题

https://ac.nowcoder.com/acm/problem/15163

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

const int maxn = 1e5 + 9;

int a[maxn], t[maxn], n;

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

void add(int k, int x)//给点k加上值x
{
    //点k所在的第一个区间是k（最下面这个区间）
    for(int i = k;i <= n; i += lowbit(i))t[i] += x;
}

int getsum(int k)//返回原数组a中区间[1, k]的和
{
    int res = 0;
    for(int i = k;i > 0; i -= lowbit(i))res += t[i];
    return res;
}


signed main()
{
    scanf("%lld", &n);

    for(int i = 1;i <= n; ++ i)scanf("%lld", a + i);

    int ans = 0;
    for(int i = 1;i <= n; ++ i)
    {
        //把值在[a[i] + 1, ...)的所有个数加起来

        ans += i - 1 - getsum(a[i]);
        add(a[i], 1);
    }

    printf("%lld\n", ans);
    return 0;
}

https://ac.nowcoder.com/acm/problem/15175

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

const int maxn = 1e5 + 9;

int a[maxn], d[maxn], di_1[maxn], n, m;

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

void add(int k, int x)//给点k加上值x
{

    //d[] += x, di_1[] += x * (k - 1)
    //点k所在的第一个区间是k（最下面这个区间）
    for(int i = k;i <= n; i += lowbit(i))d[i] += x, di_1[i] += x * (k - 1);
}

int getsum(int k)//返回原数组a中区间[1, k]的和
{
    int res = 0;
    for(int i = k;i > 0; i -= lowbit(i))res += k * d[i] - di_1[i];
    return res;
}


signed main()
{
    scanf("%lld %lld", &n, &m);

    for(int i = 1;i <= n; ++ i)scanf("%lld", a + i);

    for(int i = 1;i <= n; ++ i)add(i, a[i]), add(i + 1, -a[i]);

    while(m --)
    {
        char s[5];scanf("%s", s);
        char op = s[0];

        if(op == 'Q')
        {
            int l, r;scanf("%lld %lld", &l, &r);
            printf("%lld\n", getsum(r) - getsum(l - 1));
        }
        else if(op == 'C')
        {
            int l, r, v;scanf("%lld %lld %lld", &l, &r, &v);
            add(l, v), add(r + 1, -v);
        }
    }

    return 0;
}

天梯赛L3-1

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e6 + 9;
int n, m, t[maxn];

struct Q
{
    int l, r, v;
    bool operator < (const Q &b)const
    {
        return r < b.r;
    }
}q[maxn];//m个查询

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

void add(int k, int x)//在点k上增加x
{
    for(int i = k;i <= n;i += lowbit(i))t[i] += x;
}

int getsum(int k)//返回[1, k]的和
{
    int res = 0;

    for(int i = k;i ; i -= lowbit(i))res += t[i];

    return res;
}

signed main()
{
    scanf("%lld %lld", &n, &m);

    for(int i = 1;i <= m; ++ i)
        scanf("%lld %lld %lld", &q[i].l, &q[i].r, &q[i].v);

    sort(q + 1,q + 1 + m);//r升序

    for(int i = 1;i <= m; ++ i)
    {
        int l = q[i].l, r = q[i].r, v = q[i].v;

        int sum = getsum(r) - getsum(l - 1);
        if(sum < v)add(r, v - sum);
    }

    for(int i = 1;i <= n; ++ i)
        printf("%lld ", getsum(i) - getsum(i - 1));

    return 0;
}