打算在 pushdown 的时候开左右两个儿子,但是好像没法获得每个儿子的区间之和。。
请问 pushdown 应该怎么写?
#include <vector>
#include <iostream>
typedef long long lint;
const int N = 1e5 + 10;
template <typename T>
struct Pool {
std::vector<T *> buf;
T *create() {
buf.push_back(new T);
return buf.back();
}
void dispose() {
for (size_t i = 0; i < buf.size(); ++i) delete buf[i];
buf.clear();
}
};
struct TreeNode {
int l, r;
lint sum, lzy;
TreeNode *lson, *rson;
};
int n, m;
lint a[N];
bool inRange(TreeNode *u, int L, int R) {
return u->l >= L && u->r <= R;
}
bool outRange(TreeNode *u, int L, int R) {
return u->l > R || u->r < L;
}
void maketag(TreeNode *u, lint x) {
u->w += x * (u->r - u->l + 1);
u->lzy += x;
}
void pushup(TreeNode *u) {
u->w = u->lson->w + u->rson->w;
}
void pushdown(TreeNode *u) {
}
lint query(TreeNode *u, int L, int R) {
if (outRange(u, L, R)) return 0;
if (inRange(u, L, R)) return u->w;
pushdown(u);
return query(u->lson, L, R) + query(u->rson, L, R);
}
void update(TreeNode *u, int L, int R, lint x) {
if (outRange(u, L, R)) return ;
if (inRange(u, L, R)) { maketag(u, x); return ; }
pushdown(u);
update(u->lson, L, R, x);
update(u->rson, L, R, x);
pushup(u);
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
std::cin >> n >> m;
for (int i = 1; i <= n; ++i) std::cin >> a[i];
return 0;
}