萌新求助线段树
查看原帖
萌新求助线段树
107253
Water_Cows楼主2021/2/14 17:35
#include <iostream>
using namespace std;

const int N = 1e5 + 7;

struct tree
{
    int l, r, sum;
} e[N<<2];

inline void Build(int x, int l, int r)
{
    e[x].l = l, e[x].r = r;
    if(l == r) 
        return ;
    int mid = (l + r >> 1);
    Build(x << 1, l, mid);
    Build((x << 1) + 1, mid + 1, r); 
}

inline void add(int x, int point, int k)
{
    if(e[x].l == e[x].r) {
        e[x].sum += k;
        return ;
    }
    if(point <= e[x << 1].r) add(x << 1, point, k);
    else add((x << 1) + 1, point, k);
    e[x].sum = e[x << 1].sum + e[(x << 1) + 1].sum;
}

inline int query(int x, int l, int r)
{
    if(e[x].l >= l && e[x].r <= r)
        return e[x].sum;
    if(e[x].l < l && e[x].r > r)
        return 0;
    int sum = 0;
    if(e[x << 1].r >= l) sum += query(x << 1, l, r);
    if(e[(x << 1) + 1].l <= r) sum += query((x << 1) + 1, l, r);
    return sum;
}

int n, k;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;
    Build(1, 1, n);
    for(int i=1; i<=k; i++)
    {
        char opt; cin >> opt;
        if(opt == 'x') {
            int x, k; cin >> x >> k;
            add(1, x, k);
        }
        else if(opt == 'y') {
            int l, r; cin >> l >> r;
            cout << query(1, l, r) << '\n';
        }
    }
    return 0;
}

刚学线段树,求 Dalao 差错。

2021/2/14 17:35
加载中...