树状数组

C++ 代码

#include<bits/stdc++.h>

using namespace std;

const int N = 100010;

int a[N], tr[N];

int n, m;

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

void add(int x, int v)  //第x个位置的数字加上v
{
    for(int i=x; i<=n; i+= lowbit(i))   tr[i] += v;
}

int query(int x)  //求前i个数的和
{
    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]);  //数组初始值为0，这里相当于初始化

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

    return 0;

}

线段树

C++ 代码

#include<bits/stdc++.h>

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)  //给节点u的sum赋初值
{
    tr[u].sum = tr[2*u].sum + tr[2*u+1].sum;
}

void build(int u, int l, int r)  //初始化线段树，u为根节点，l，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) //查询从u节点开始，[l,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)  //从u结点开始，在x结点上加上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;
}