树状数组

树状数组是使用一个一维数组，维护一个多叉树，支持在线修改的求前缀和的数据结构。

下图是树状数组的构成图：

目前还不会树状数组的原理，只会使用 : )

模板题

给定 n个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。

输入格式

第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。

第二行包含 n个整数，表示完整数列。

接下来 m行，每行包含三个整数 k,a,b,（k=0，表示求子数列[a,b]的和；k=1，表示第 a个数加 b）。

数列从 11 开始计数。

输出格式

输出若干行数字，表示 k=0 时，对应的子数列 [a,b] 的连续和。

数据范围

1≤n≤100000, 1≤m≤100000， 1≤a≤b≤n, 数据保证在任何时候，数列中所有元素之和均在 int 范围内。

输入样例

10 5
1 2 3 4 5 6 7 8 9 10
1 1 5
0 1 3
0 4 8
1 7 5
0 4 8

输出样例

11
30
35

代码

#include <stdio.h>
#include <iostream>
using namespace std;
const int N = 100010;
int n, m;
int a[N], tr[N];

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

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

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

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

    while(m--)
    {
        int k, x, y;
        cin >> k >> x >> y;
        if(k == 0) cout << query(y) - query(x - 1) << endl;
        else add(x, y);
    }

    return 0;
}

线段树

线段树的用处比树状数组要广，它可以用来维护一段区间内的信息，像最大值，区间和等等。正如它的名字，他是由一个一个的线段构成的树，下图是一个例子：

构建

通常使用结构体来存放节点，使用类似于堆存储的方式存储树的结构。

对于构建过程有以下步骤：

从根节点开始：

1. 判断当前构建节点左右端点是否相等，相等就直接赋值，否则继续
2. 计算中间值，递归的构建左右子区间
3. 回溯时进行pushup操作

pushup

pushup操作被定义为维护（更新）当前节点的信息，当节点中维护的是最大值时：tr[u].maxv = tr[u << 1].maxv, tr[u << 1 | 1].maxv。

查询

假设我们要求2到5的区间和，求法如下：

从根节点开始，

1. 判断当前节点是否被所询问区间覆盖，覆盖就直接返回，如果没有覆盖继续
2. 判断所询问区间和中点的关系，根据关系条件递归的询问两个子区间
3. 如果递归到了叶子节点，就直接返回。

修改

修改有以下步骤：

从根节点开始：

1. 判断当前节点是否是要修改的节点是的话直接修改并返回，不是就继续
2. 判断所询问位置和中点的关系，根据关系条件递归的修改两个子区间值
3. 回溯的时候进行pushup操作

题目和上面的相同，下面是代码

代码

#include <iostream>
using namespace std;
const int N = 100010;
struct
{
    int l, r;
    int sum;
}tr[N * 4];
int n, m;
int w[N];

void pushup(int u)
{
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}
void build(int u, int l, int r)
{
    if(l == r) tr[u] = {l, r, w[r]};
    else
    {
        tr[u] = {l, r};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

int query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    int mid = tr[u].l + tr[u].r >> 1;
    int sum = 0;
    if (l <= mid) sum = query(u << 1, l, r);
    if (r > mid) sum += query(u << 1 | 1, l, r);
    return sum;
}

void modify(int u, int x, int v)
{
    if(tr[u].l == tr[u].r) tr[u].sum += v;
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++) cin >> w[i];
    build(1, 1, n);
    while(m --)
    {
        int k, a, b;
        cin >> k >> a >> b;
        if(k == 0) cout << query(1, a, b) << endl;
        else modify(1, a, b);
    }
    return 0;
}