社区讨论
怎么把函数当参数传到函数里
灌水区参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @lzo5o3dl
- 此快照首次捕获于
- 2024/08/10 21:12 2 年前
- 此快照最后确认于
- 2024/08/10 22:16 2 年前
想水一个线段树模板
CPP
#include <vector>
#include <iostream>
using namespace std;
template<typename T>
struct SegmentTree {
public:
vector<T> arr;
vector<T> tree;
vector<T> tag;
inline size_t ls(size_t x) const { return x << 1; }
inline size_t rs(size_t x) const { return x << 1 | 1; }
void push_up(size_t p) {
tree[p] = tree[ls(p)] + tree[rs(p)];
}
void build(size_t p, size_t l, size_t r) {
tag[p] = 0;
if (l == r) {
tree[p] = arr[l];
return;
}
size_t mid = (l + r) >> 1;
build(ls(p), l, mid);
build(rs(p), mid + 1, r);
push_up(p);
}
inline void apply_tag(size_t p, size_t l, size_t r, T k) {
tag[p] += k;
tree[p] += k * (r - l + 1);
}
void push_down(size_t p, size_t l, size_t r) {
size_t mid = (l + r) >> 1;
apply_tag(ls(p), l, mid, tag[p]);
apply_tag(rs(p), mid + 1, r, tag[p]);
tag[p] = 0;
}
void update(size_t p, size_t nl, size_t nr, size_t l, size_t r, T k) {
if (nl <= l && r <= nr) {
apply_tag(p, l, r, k);
return;
}
push_down(p, l, r);
size_t mid = (l + r) >> 1;
if (nl <= mid) update(ls(p), nl, nr, l, mid, k);
if (nr > mid) update(rs(p), nl, nr, mid + 1, r, k);
push_up(p);
}
T query(size_t p, size_t x, size_t y, size_t l, size_t r) {
if (x <= l && r <= y) return tree[p];
size_t mid = (l + r) >> 1;
push_down(p, l, r);
T res = 0;
if (x <= mid) res += query(ls(p), x, y, l, mid);
if (y > mid) res += query(rs(p), x, y, mid + 1, r);
return res;
}
public:
SegmentTree(size_t size)
: arr(size + 1), tree(4 * size), tag(4 * size) {}
};
int main() {
size_t n, m;
cin >> n >> m;
SegmentTree<long long> tree(n);
for (size_t i = 1; i <= n; i++) {
cin >> tree.arr[i];
}
tree.build(1, 1, n);
while (m--) {
int o;
cin >> o;
if (o == 1) {
int x, y, k;
cin >> x >> y >> k;
tree.update(1, x, y, 1, n, k);
}
else {
int x, y;
cin >> x >> y;
cout << tree.query(1, x, y, 1, n) << endl;
}
}
return 0;
}
本来想让每个函数传进去一个函数,自定义线段树的 行为,但是我不知道怎么传函数进去。所以有大佬会吗。
回复
共 0 条回复,欢迎继续交流。
正在加载回复...