树状数组

根据操作来选取数据结构
时间复杂度$O(log_n)$
可以实现的功能：
1.将某个位置上的数加上一个数
2.求某一个前缀和

$lowbit$函数操作是求出非负整数x的最后一位1所表示的数值。也就是一个二进制数末尾的0的个数为k，那么$lowbit = 2^k$。

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

树状数组的每一个c[x] = (x - lowbit(x), x], k 代表层数。

求前x项的前缀和是一个递归过程，不断缩小(x - lowbit(x), x]这个区间。

int res = 0;
for (int i = x; i > 0; i -= lowbit(i)) res += c[i];

return res;

加上一个数，更新前缀和
for (int i = x; i <= n; i += lowbit(i)) c[x] += v
如果当前结点为x，那么他的父结点就是 x + lowbit(x)也就是 x + (x & -x)。
![7JVDV_$K]@L8A3UJ](}3[DS.png](https://cdn.acwing.com/media/article/image/2022/02/26/125043_0dd15dea96-7JVDV_$K]@L8A3UJ](}3[DS.png)

线段树

操作：
1.单点修改 $O(log_n)$
2.区间查询 $O(log_n)$
函数说明
1.pushup用子结点的信息来更新当前结点的信息
2.build在一段区间上初始化线段树
3.modify修改
4.query查询

以动态求连续区间和为例

树状数组的写法

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

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 x, int v)
{
    for (int i = x; i <= n; i += lowbit(i)) tr[i] += v;
}

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

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]);

    while (m -- )
    {
        int k, x, y;
        scanf("%d%d%d", &k, &x, &y);
        if (k == 0) printf("%d\n", query(y) - query(x - 1));
        else add(x, y);
    }

    return 0;
}

线段树的写法

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

using namespace std;

const int N = 100010;

int n, m;
int w[N];
struct Node
{
    int l, r;
    int sum;
}tr[N * 4];

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()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
    build(1, 1, n);

    int k, a, b;
    while (m -- )
    {
        scanf("%d%d%d", &k, &a, &b);
        if (k == 0) printf("%d\n", query(1, a, b));
        else modify(1, a, b);
    }

    return 0;
}