基本

自我觉得最重要的:

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

更新

// 更新树状数组 x += lowbit(x) 代表x的父节点
// 初始化用更新来实现
void update(int x,int k)
{
    for (; x <= n; x += lowbit(x)) c[x] += k;
}

查询

// 前缀和查询
int getsum(int x)
{
    int res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
}

例题

区间更新+单点查询

可以用树状数组来维护一个差分数组,那树状数组本身就是原数组(因为差分求一遍前缀和即为原数组)

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 500050;

int n, m;
int c[N], a[N];

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

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

int query(int x)
{
    int res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
}

int main()
{
    scanf ("%d %d", &n, &m);

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

    while (m --)
    {
        int q, x, k;

        scanf ("%d", &q);

        if (q == 1) 
        {
            int x, y, k;
            scanf ("%d %d %d", &x, &y, &k);
            update(x, k), update(y + 1, -k);
        }
        else
        {
            scanf ("%d", &x);
            printf ("%d\n", query(x));
        }
    }

    return 0;
}

逆序对

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 500050;

int n;
int b[N];
int c[N];
struct node
{
    int v, id;
    bool operator < (const node &A) const // 我们重载一下小于号
    {
        if (v != A.v) return v < A.v; // 如果值不一样,那就按从小到大排序
        return id < A.id; // 如果有相同的值,让先出现的排在前面,这样会避免出错
    }
}a[N];

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

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

int query(int x)
{
    int res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
}

int main()
{
    scanf ("%d", &n);

    for (int i = 1; i <= n; i ++)
    {
        scanf ("%d", &a[i].v);
        a[i].id = i;
    }
    // 离散化操作
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i ++) b[a[i].id] = i;

    LL res = 0;

    for (int i = 1; i <= n; i ++)
    {
        insert(b[i], 1);
        res = res + (LL) i - query(b[i]); // 询问的是前i - 1个数有多少个数比b[i]小(顺序对)
    }
    printf ("%lld", res);
    return 0;
}

Messenger Simulator

好题就是我想不到

又是一题把数字1用的活灵活现的题
初始化时,我们把所有点的位置往后移m位(为了后面将某个点提前做准备)
然后值赋为1,我们只需要有多少个点在这个点的前面就行,那就可以用树状数组维护一下前缀和
更重要的是
    一个点的最小位置只可能是1或者初始位置
    一个点的最大位置只可能是在移动它之前的位置和做完所有操作以后它的位置
所以我们在每次移动的时候都更新一次最大值
最后在所有操作结束后更新一下所有点的最大值即可

$$ 时间复杂度O(N + M) $$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 300300;

int n, m;
int Max[N], Min[N], pos[N];
int c[N << 1];

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

void insert(int x, int k)
{
    for (; x <= n + m; x += lowbit(x)) c[x] += k;
}

int query(int x)
{
    int res = 0;
    for (; x; x -= lowbit(x)) res += c[x];
    return res;
}

int main()
{
    scanf ("%d %d", &n, &m);

    for (int i = 1; i <= n; i ++)
    {
        Max[i] = Min[i] = i;
        pos[i] = m + i;
        insert(pos[i], 1);
    }

    int t = m; // 移动到哪个位置
    for (int k = 1; k <= m; k ++) // 这里不能写while(m --)因为insert里要用到m
    {
        int i;
        scanf ("%d", &i);
        Min[i] = 1;
        Max[i] = max(Max[i], query(pos[i]));
        insert(pos[i], -1); // 先要让后面那个位置无效
        pos[i] = t --; // 然后再按一个个顺序往前移
        insert(pos[i], 1);
    }

    for (int i = 1; i <= n; i ++) Max[i] = max(Max[i], query(pos[i]));
    for (int i = 1; i <= n; i ++)
        printf ("%d %d\n", Min[i], Max[i]);
    return 0;
}

计数问题

注释重点大坑

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 303, M = 101;

int n, m, Q;
int c[N][N][M];
int g[N][N];

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

void insert(int x, int y, int z, int k)
{
    // 这里用x和y直接求,然后改到亖也改不出来哪错了
    // 一定要记住(呜呜呜)
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= m; j += lowbit(j))
            c[i][j][z] += k;
    // 简单说下原因
    // 就是如果单独用x, y的话,y如果小于m,在x第一次循环后y=m,然后y就一直不变了
}

int query(int x, int y, int z)
{
    // 同上
    int res = 0;
    for (int i = x; i; i -= lowbit(i))
        for (int j = y; j; j -= lowbit(j))
            res += c[i][j][z];
    return res;
}

int main()
{
    scanf ("%d %d", &n, &m);

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= m; j ++)
        {
            scanf ("%d", &g[i][j]);
            insert(i, j, g[i][j], 1);
        }

    scanf ("%d", &Q);
    while (Q --)
    {
        int op;
        scanf ("%d", &op);
        if (op == 1)
        {
            int x, y, k;
            scanf ("%d %d %d", &x, &y, &k);
            insert(x, y, g[x][y], -1);
            g[x][y] = k;
            insert(x, y, g[x][y], 1);
        }
        else
        {
            int x1, x2, y1, y2, k;
            scanf ("%d %d %d %d %d", &x1, &x2, &y1, &y2, &k);
            printf ("%d\n", query(x2, y2, k) - query(x1 - 1, y2, k) - query(x2, y1 - 1, k) + query(x1 - 1, y1 - 1, k));
        }
    }
    return 0;
}

HH的项链

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1000010;

int n, m;
int loc[N], a[N];
int sum[N << 2];

struct query
{
    int l, r, res, id;
}e[N];

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

bool cmp1(query A, query B)
{
    return A.r < B.r;
}

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

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

bool cmp2(query A, query B)
{
    return A.id < B.id;
}

int main()
{
    scanf ("%d", &n);

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

    scanf ("%d", &m);
    for (int i = 0; i < m; i ++)
    {
        scanf ("%d %d", &e[i].l, &e[i].r);
        e[i].id = i;
    }
    // 先按查询区间右端点排序
    sort(e, e + m, cmp1);

    int tmp = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (tmp >= m) break; // 如果答案已经全部找出来了就不需要再继续了
        if (!loc[a[i]]) // 如果前面没有出现过这个种类
        {
            insert(i, 1); 
            loc[a[i]] = i; // 表示这个种类出现过并且记录其位置
        }
        else // 如果前面已经出现过这个种类了
        {
            insert(loc[a[i]], -1); // 前面那个种类在后续的查询中就无效了(因为此时区间是按右端点排序的)
            loc[a[i]] = i;
            insert(i, 1);
        }
        // 这里一定要写while,因为可能有很多区间的右端点相同
        while (i == e[tmp].r) e[tmp].res = get(e[tmp].r) - get(e[tmp].l - 1), tmp ++;
    }
    // 再按询问的顺序排序一遍即可
    sort(e, e + m, cmp2);

    for (int i = 0; i < m; i ++) printf ("%d\n", e[i].res);

    return 0;
}