单点修改+区间查询线段树
这个没有标记，还是比较好写的。
//P3374 【模板】树状数组 1#include <bits/stdc++.h>using namespace std;#define LL long longconst int N = 1000010;struct Node {int l, r;LL sum;} a[N << 2];#define ls(x) (x << 1)#define rs(x) (x << 1 | 1)inline void pushup(int x) {a[x].sum = a[ls(x)].sum + a[rs(x)].sum;}void build(int x, int l, int r){a[x].l = l, a[x].r = r;if (l == r) {scanf("%lld", &a[x].sum);return;}int mid = (l + r) >> 1;build(ls(x), l, mid);build(rs(x), mid + 1, r);pushup(x);}LL query(int x, int l, int r) {if (l <= a[x].l && a[x].r <= r)return a[x].sum;int mid = (a[x].l + a[x].r) >> 1;LL res = 0;if (l <= mid) res += query(ls(x), l, r);if (r > mid) res += query(rs(x), l, r);return res;}void change(int x, int p, LL val) {if (a[x].l == a[x].r) {a[x].sum += val;return;}int mid = (a[x].l + a[x].r) >> 1;if (p <= mid) change(ls(x), p, val);if (p > mid) change(rs(x), p, val);pushup(x);}
对于单点修改，除了从根节点向下找，我们还可以从叶子节点向上修改，如下：
int mp[N];
//mp记录的是某叶子节点在线段树对应的节点的序号，可以在build的时候一并算出
//在l==r的时候记mp[l] = x 或者 mp[r] = x 即可
//这种写法虽然要多开一个mp数组，但是写起来快，而且跑的速度常数也要小一些
void change(int p, LL val) {
int x = mp[p];
a[x].sum += val;
while (x >>= 1) pushup(x);
}
区间修改+区间查询线段树
//P3372
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 100010;
int n, m;
struct node {
int l, r, len;
LL val, tag;
} a[N << 2];
inline int ls(int x) { return x << 1; };
inline int rs(int x) { return x << 1 | 1; };
inline void pushup(int x) {
a[x].val = a[ls(x)].val + a[rs(x)].val;
}
void build(int x = 1, int l = 1, int r = n) {
a[x].l = l, a[x].r = r, a[x].len = r - l + 1;
if (l == r) {
scanf("%lld", &a[x].val);
return;
}
int mid = (l + r) >> 1;
build(ls(x), l, mid);
build(rs(x), mid + 1, r);
pushup(x);
}
inline void f(int x, int k) {
a[x].tag += k;
a[x].val += k * a[x].len;
}
inline void pushdown(int x) {
f(ls(x), a[x].tag);
f(rs(x), a[x].tag);
a[x].tag = 0;
}
void update(int l, int r, LL val, int x);
LL query(int l, int r, int x);
int main()
{
scanf("%d%d", &n, &m);
build();
while (m--) {
int opt, l, r;
scanf("%d%d%d", &opt, &l, &r);
if (opt == 1) {
LL val;
scanf("%lld", &val);
update(l, r, val, 1);
}
else printf("%lld\n", query(l, r, 1));
}
return 0;
}
void update(int l, int r, LL val, int x)
{
if (l <= a[x].l && a[x].r <= r) {
a[x].val += a[x].len * val;
a[x].tag += val;
return;
}
pushdown(x);
int mid = (a[x].l + a[x].r) >> 1;
if (l <= mid) update(l, r, val, ls(x));
if (r > mid) update(l, r, val, rs(x));
pushup(x);
return;
}
LL query(int l, int r, int x)
{
if (l <= a[x].l && a[x].r <= r)
return a[x].val;
pushdown(x);
int mid = (a[x].l + a[x].r) >> 1;
LL ans = 0;
if (l <= mid) ans += query(l, r, ls(x));
if (r > mid) ans += query(l, r, rs(x));
return ans;
}
多标记线段树
下面给出一个同时处理区间加，区间乘，和查询区间和的线段树模板。
（本质上就是多存几个tag，维护好他们的先后关系，查询或者修改的时候记得下传即可）
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
#define LL long long
//题目中给的p，作为模数的，从数据中读入
int p;
LL a[N];
//线段树结构体，v表示此时的答案，mul表示乘法意义上的lazytag，add是加法意义上的
struct Node {
int l, r, len;
LL v, mul, add;
} st[N << 2];
inline int ls(int x) { return x << 1; }
inline int rs(int x) { return x << 1 | 1; }
//buildtree
inline void pushup(int x) {
st[x].v = (st[ls(x)].v + st[rs(x)].v) % p;
}
void build (int x, int l, int r) {
Node &node = st[x];
node.mul = 1, node.add = 0;
node.l = l, node.r = r, node.len = r - l + 1;
if (l == r) {
node.v = a[l];
return;
}
int mid = (l + r) / 2;
build(ls(x), l, mid);
build(rs(x), mid + 1, r);
pushup(x);
}
//核心代码，维护lazytag
void solve(int x, LL k1, LL k2) {
Node &node = st[x];
node.v = (node.v * k1 + k2 * node.len) % p;
node.mul = (node.mul * k1) % p;
node.add = (node.add * k1 + k2) % p;
}
void pushdown(int x) {
solve(ls(x), st[x].mul, st[x].add);
solve(rs(x), st[x].mul, st[x].add);
st[x].mul = 1, st[x].add = 0;
}
//update1:乘法
void update1(int x, int l, int r, LL k) {
if (l <= st[x].l && st[x].r <= r) {
solve(x, k, 0);
return;
}
pushdown(x);
int mid = (st[x].l + st[x].r) / 2;
if (l <= mid) update1(ls(x), l, r, k);
if (r > mid) update1(rs(x), l, r, k);
pushup(x);
}
//update2，加法，和乘法同理
void update2(int x, int l, int r, LL k) {
if (l <= st[x].l && st[x].r <= r) {
solve(x, 1, k);
return;
}
pushdown(x);
int mid = (st[x].l + st[x].r) / 2;
if (l <= mid) update2(ls(x), l, r, k);
if (r > mid) update2(rs(x), l, r, k);
pushup(x);
}
//query:查询
long long query(int x, int l, int r)
{
if (l <= st[x].l && st[x].r <= r) return st[x].v;
pushdown(x);
int mid = (st[x].l + st[x].r) / 2, res = 0;
if (l <= mid) res += query(ls(x), l, r);
if (r > mid) res += query(rs(x), l, r);
return res % p;
}
带暴力的线段树
考虑一种需要区间开根号的操作（向下取整）的线段树，怎么写？
对于一个int类型的数，至多开个10次就差不多变成1或者0了，而这两个数显然不管之后怎么开，值都不会变化。
那么，我们想到一种暴力的策略：正常情况下，每次操作的时候都直接进行比较暴力的修改（多次单点修改罢了），但是与此同时，我们给每个区间做一个标记，这个标记记录了该区间的值是否是全0或者全1，如果修改的时候碰到这种区间，那么就不操作，直接返回。
显然，每个数至多被开五六次平方，每个数被开方的复杂度都是
的，所以总复杂度在 
这样，并不会超时（K 是开方的次数，如上所示，是一个很小的常数）。
这种线段树又被称作势能线段树（因为不管局部操作的复杂度是否正确，但是整体复杂度不变），不仅可以处理开方，也可以用来处理其他的可以使得一个数快速收敛的操作，例如lowbit操作。
//P4145 上帝造题的七分钟 2 / 花神游历各国
#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 100010;
struct tree {
int l, r;
LL sum;
bool flag;
} a[N << 2];
#define ls(x) (x << 1)
#define rs(x) (x << 1 | 1)
void pushup(int x)
{
a[x].sum = a[ls(x)].sum + a[rs(x)].sum;
a[x].flag = (a[ls(x)].flag && a[rs(x)].flag);
}
void build(int x, int l, int r)
{
a[x].l = l, a[x].r = r;
if (l == r) {
scanf("%lld", &a[x].sum);
return;
}
int mid = (l + r) >> 1;
build(ls(x), l, mid);
build(rs(x), mid + 1, r);
pushup(x);
}
LL query(int x, int l, int r) {
if (l <= a[x].l && a[x].r <= r)
return a[x].sum;
int mid = (a[x].l + a[x].r) >> 1;
LL res = 0;
if (l <= mid) res += query(ls(x), l, r);
if (r > mid) res += query(rs(x), l, r);
return res;
}
void change(int x, int l, int r) {
if (a[x].flag) return;
if (a[x].l == a[x].r) {
a[x].sum = sqrt(a[x].sum);
a[x].flag = (a[x].sum == 0 || a[x].sum == 1);
return;
}
int mid = (a[x].l + a[x].r) >> 1;
if (l <= mid) change(ls(x), l, r);
if (r > mid) change(rs(x), l, r);
pushup(x);
}
若有收获，就点个赞吧
0 人点赞
