首先先上模板
(1)区间查询,单点修改
#define ls u << 1
#define rs u << 1 | 1
struct SegTree{
struct Node{
// to do
};
vector<int> w;
vector<Node> tr;
SegTree(int n) :tr(n * 4 + 1), w(n + 1){}
void pushup(Node& u, Node& l, Node& r){
// to do
}
void pushup(int u){
pushup(tr[u], tr[ls], tr[rs]);
}
void build(int u, int l, int r){
tr[u] = {l, r};
if(l == r)
{
// to do
return;
}
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
void modify(int u, int idx, int val){
if(tr[u].l == tr[u].r && tr[u].l == idx)
{
// to do
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(idx <= mid) modify(ls, idx, val);
else
modify(rs, idx, val);
pushup(u);
}
Node query(int u, int L, int R){
if(tr[u].l >= L && tr[u].r <= R)
return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if(R <= mid) return query(ls, L, R);
else if (L > mid) return query(rs, L, R);
else
{
// to do
}
}
};
(2) 区间查询,区间修改
#define int long long
#define ls u << 1
#define rs u << 1 | 1
struct SegTree{
struct Node{
// to do
};
vector<int> w;
vector<Node> tr;
SegTree(int n) :tr(n * 4 + 1), w(n + 1){}
void pushdown(Node& u, Node& l, Node& r){
// to do
}
void pushup(Node& u, Node& l, Node& r){
// to do
}
void pushup(int u){
pushup(tr[u], tr[ls], tr[rs]);
}
void pushdown(int u){
pushdown(tr[u], tr[ls], tr[rs]);
}
void build(int u, int l, int r){
tr[u] = {l, r};
if(l == r)
{
// to do
return;
}
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
void eval(Node& t, int add, int mul){
// to do
}
void modify(int u, int idx, int val){ // 单点修改
if(tr[u].l == tr[u].r && tr[u].l == idx)
{
// to do
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(idx <= mid) modify(ls, idx, val);
else
modify(rs, idx, val);
pushup(u);
}
void modify(int u, int L, int R, int val) // 区间修改
{
if(tr[u].l >= L && tr[u].r <= R)
{
// to do
// eval(tr[u], val);
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(L <= mid) modify(ls, L, R, val);
if(R > mid) modify(rs, L, R, val);
pushup(u);
}
Node query(int u, int L, int R){
if(tr[u].l >= L && tr[u].r <= R)
return tr[u];
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(R <= mid) return query(ls, L, R);
else if (L > mid) return query(rs, L, R);
else
{
// to do
}
}
};
关于模板的使用
- 在用模板时只需要在
// to do
下面填入相应的操 - 对于单点修改的核心是写对pushup()函数
简单
- 对于区间修改的核心是写对eval()函数
困难
- 下面具体看几道例题体会一下该模板的便捷性
1275. 最大数
单点修改 区间查询
#include <bits/stdc++.h>
using namespace std;
#define ls u << 1
#define rs u << 1 | 1
#define int long long
struct SegTree{
struct Node{
// to do
int l, r;
int maxv;
};
vector<int> w;
vector<Node> tr;
SegTree(int n) :tr(n * 4 + 1), w(n + 1){}
void pushup(Node& u, Node& l, Node& r){
// to do
u.maxv = max(l.maxv, r.maxv);
}
void pushup(int u){
pushup(tr[u], tr[ls], tr[rs]);
}
void build(int u, int l, int r){
tr[u] = {l, r};
if(l == r)
{
// to do
return;
}
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
void modify(int u, int idx, int val){
if(tr[u].l == tr[u].r && tr[u].l == idx)
{
// to do
tr[u].maxv = val;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(idx <= mid) modify(ls, idx, val);
else
modify(rs, idx, val);
pushup(u);
}
Node query(int u, int L, int R){
if(tr[u].l >= L && tr[u].r <= R)
return tr[u];
int mid = tr[u].l + tr[u].r >> 1;
if(R <= mid) return query(ls, L, R);
else if (L > mid) return query(rs, L, R);
else
{
// to do
auto left = query(ls, L, R);
auto right = query(rs, L, R);
Node res;
pushup(res, left, right);
return res;
}
}
};
signed main(){
ios::sync_with_stdio(false);
std::cin.tie(0);
int n, p; cin >> n >> p;
int idx = 0, last = 0;
SegTree se(n);
se.build(1, 1, n);
while(n --)
{
string op; cin >> op;
int x; cin >> x;
if(op == "A")
se.modify(1, ++ idx, (x + last) % p);
else
last = se.query(1, idx - x + 1, idx).maxv, cout << last << "\n";
}
return 0;
}
243. 一个简单的整数问题2
区间修改 区间查询
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ls u << 1
#define rs u << 1 | 1
struct SegTree{
struct Node{
// to do
int l, r;
int sum, add;
};
vector<int> w;
vector<Node> tr;
SegTree(int n) :tr(n * 4 + 1), w(n + 1){}
void pushdown(Node& u, Node& l, Node& r){
// to do
if(u.add)
{
int add = u.add;
eval(l, add);
eval(r, add);
u.add = 0;
}
}
void pushup(Node& u, Node& l, Node& r){
// to do
u.sum = l.sum + r.sum;
}
void pushup(int u){
pushup(tr[u], tr[ls], tr[rs]);
}
void pushdown(int u){
pushdown(tr[u], tr[ls], tr[rs]);
}
void build(int u, int l, int r){
tr[u] = {l, r};
if(l == r)
{
// to do
tr[u] = {l, l, w[l], 0};
return;
}
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
void eval(Node& t, int add){
// to do
t.add += add, t.sum += (t.r - t.l + 1) * add;
}
void modify(int u, int L, int R, int val) // 区间修改
{
if(tr[u].l >= L && tr[u].r <= R)
{
// to do
eval(tr[u], val);
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(L <= mid) modify(ls, L, R, val);
if(R > mid) modify(rs, L, R, val);
pushup(u);
}
Node query(int u, int L, int R){
if(tr[u].l >= L && tr[u].r <= R)
return tr[u];
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(R <= mid) return query(ls, L, R);
else if (L > mid) return query(rs, L, R);
else
{
// to do
auto l = query(ls, L, R);
auto r = query(rs, L, R);
Node res;
pushup(res, l, r);
return res;
}
}
};
signed main(){
ios::sync_with_stdio(false);
std::cin.tie(0);
int n, m; cin >> n >> m;
SegTree se(n);
for(int i = 1; i <= n; i ++) cin >> se.w[i];
se.build(1, 1, n);
while(m --)
{
string op; cin >> op;
if(op == "C")
{
int l, r, d; cin >> l >> r >> d;
se.modify(1, l, r, d);
}
else
{
int l, r; cin >> l >> r;
cout << se.query(1, l, r).sum << "\n";
}
}
return 0;
}
1277. 维护序列
区间修改 区间查询
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ls u << 1
#define rs u << 1 | 1
struct SegTree{
struct Node{
// to do
int l, r;
int sum;
int add, mul;
};
int p;
vector<int> w;
vector<Node> tr;
SegTree(int n, int _p) :tr(n * 4 + 1), w(n + 1), p(_p){}
void pushdown(Node& u, Node& l, Node& r){
// to do
eval(l, u.add, u.mul);
eval(r, u.add, u.mul);
u.add = 0, u.mul = 1;
}
void pushup(Node& u, Node& l, Node& r){
// to do
u.sum = (l.sum + r.sum) % p;
}
void pushup(int u){
pushup(tr[u], tr[ls], tr[rs]);
}
void pushdown(int u){
pushdown(tr[u], tr[ls], tr[rs]);
}
void eval(Node &t, int add, int mul)
{
t.sum = (t.sum * mul + (t.r - t.l + 1) * add) % p;
t.mul = t.mul * mul % p;
t.add = (t.add * mul + add) % p;
}
void build(int u, int l, int r){
tr[u] = {l, r, 0, 0, 1};
if(l == r)
{
// to do
tr[u] = {l, l, w[l], 0, 1};
return;
}
int mid = l + r >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
pushup(u);
}
void modify(int u, int idx, int val){ // 单点修改
if(tr[u].l == tr[u].r && tr[u].l == idx)
{
// to do
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(idx <= mid) modify(ls, idx, val);
else
modify(rs, idx, val);
pushup(u);
}
void modify(int u, int L, int R, int add, int mul) // 区间修改
{
if(tr[u].l >= L && tr[u].r <= R)
{
// to do
eval(tr[u], add, mul);
return;
}
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(L <= mid) modify(ls, L, R, add, mul);
if(R > mid) modify(rs, L, R, add, mul);
pushup(u);
}
Node query(int u, int L, int R){
if(tr[u].l >= L && tr[u].r <= R)
return tr[u];
pushdown(u);
int mid = tr[u].l + tr[u].r >> 1;
if(R <= mid) return query(ls, L, R);
else if (L > mid) return query(rs, L, R);
else
{
// to do
auto l = query(ls, L, R);
auto r = query(rs, L, R);
Node res;
pushup(res, l, r);
return res;
}
}
};
signed main(){
ios::sync_with_stdio(false);
std::cin.tie(0);
int n, p; cin >> n >> p;
SegTree se(n, p);
for(int i = 1; i <= n; i ++) cin >> se.w[i];
se.build(1, 1, n);
int m; cin >> m;
while(m --)
{
int op; cin >> op;
if(op == 1)
{
int l, r, d; cin >> l >> r >> d;
se.modify(1, l, r, 0, d);
}
else if(op == 2)
{
int l, r, d; cin >> l >> r >> d;
se.modify(1, l, r, d, 1);
}
else
{
int l, r; cin >> l >> r;
cout << se.query(1, l, r).sum << "\n";
}
}
return 0;
}