线段树
约 297 字小于 1 分钟
2026-08-11
Links
模板说明
modify区间修改query区间查询
代码
static constexpr int maxn = 100003;
struct Node {
int l=0, r=0;
long long val=0, lazy=0;
} tr[maxn*4];
struct SegTree {
int cnt = 1;
void newNode(int u) {
if(!tr[u].l) {
tr[u].l = ++cnt;
}
if(!tr[u].r) {
tr[u].r = ++cnt;
}
}
void pushUp(int u) {
newNode(u);
tr[u].val = tr[tr[u].l].val + tr[tr[u].r].val;
}
void pushDown(int u, int l, int r) {
newNode(u);
int mid = (l + r) / 2;
tr[tr[u].l].val += tr[u].lazy * (mid - l + 1);
tr[tr[u].r].val += tr[u].lazy * (r - mid);
tr[tr[u].l].lazy += tr[u].lazy;
tr[tr[u].r].lazy += tr[u].lazy;
tr[u].lazy = 0;
}
void modify(int u, int l, int r, int ll, int rr, long long vval) {
if(ll <= l && r <= rr) {
tr[u].val += (r-l+1) * vval;
tr[u].lazy += vval;
return ;
}
newNode(u); pushDown(u, l, r);
int mid = (l + r) / 2;
if(ll <= mid) {
modify(tr[u].l, l, mid, ll, rr, vval);
}
if(rr > mid) {
modify(tr[u].r, mid+1, r, ll, rr, vval);
}
pushUp(u);
}
long long query(int u, int l, int r, int ll, int rr) {
if(ll <= l && r <= rr) {
return tr[u].val;
}
long long res = 0;
newNode(u); pushDown(u, l, r);
int mid = (l + r) / 2;
if(ll <= mid) {
res += query(tr[u].l, l, mid, ll, rr);
}
if(rr > mid) {
res += query(tr[u].r, mid+1, r, ll, rr);
}
pushUp(u);
return res;
}
};