求助线段数
  • 板块P2068 统计和
  • 楼主GregTao
  • 当前回复4
  • 已保存回复4
  • 发布时间2022/1/26 21:49
  • 上次更新2023/10/28 10:49:36
查看原帖
求助线段数
418885
GregTao楼主2022/1/26 21:49
#include<iostream>
#include<cstdio>
using namespace std;
namespace SegmentTree {
	const int LEN = 100001;
    int t[LEN << 2];
    int ls(int k) {
        return k << 1;
    }
    int rs(int k) {
        return k << 1 + 1;
    }
    int mid(int k1, int k2) {
        return (k1 + k2) / 2;
    }
    void pushUp(int k) {
        t[k] = t[ls(k)] + t[rs(k)];
    }
    void update(int k, int p, int val, int cl, int cr) {
        if (cl == cr) {
            t[k] += val;
            return;
        }
        int m = mid(cl, cr);
        if (p <= m) update(ls(k), p, val, cl, m);
        else update(rs(k), p, val, m + 1, cr);
        pushUp(k);
    }
    int query(int l, int r, int k, int cl, int cr) {
        if (l <= cl && cr <= r) {
            return t[k];
        }
        int m = mid(cl, cr), ans = 0;
        if (l <= m) ans += query(l, r, ls(k), cl, m);
        if (m < r) ans += query(l, r, rs(k), m + 1, cr);
        return ans;
    }
};
int main() {
    freopen("in", "r", stdin);
    int n, w, a, b;
    char typ;
    cin >> n >> w;
    for (int i = 1; i <= w; ++i) {
        cin >> typ >> a >> b;
        if (typ == 'x') {
            SegmentTree::update(1, a, b, 1, n);
        } else {
            cout << SegmentTree::query(a, b, 1, 1, n) << endl;
        }
    }
    return 0;
}
2022/1/26 21:49
加载中...