【信息学奥赛|数据结构模板】线段树

下面是我的线段树模板，第一篇为纯加法，第二篇为加乘结合。

#include <bits/stdc++.h>
#define MAXN 100010
using namespace std;
namespace segmentTreeWithoutEternalizing
{
#define lSon(p) p << 1
#define rSon(p) (p << 1) + 1
 long long n, m, op, x, y, k, a[MAXN];
 struct segTreeNode
 {
 long long lft, rgt; // segment posision
 long long data, lazytag; // data and lazy tag
 } segTree[MAXN << 2];
 void buildTree(long long p, long long l, long long r) // build a segment tree
 {
 segTree[p].lft = l;
 segTree[p].rgt = r;
 segTree[p].lazytag = 0;
 if (l == r)
 return (void)(segTree[p].data = a[l]);
 long long mid = l + r >> 1; // find an average of l and r
 buildTree(lSon(p), l, mid);
 buildTree(rSon(p), mid + 1, r);
 segTree[p].data = segTree[lSon(p)].data + segTree[rSon(p)].data;
 }
 void spread(long long p) // push down the lazy tag
 {
 // right son updating: push down & update segment sum
 segTree[lSon(p)].lazytag += segTree[p].lazytag;
 segTree[lSon(p)].data += (segTree[lSon(p)].rgt - segTree[lSon(p)].lft + 1) * segTree[p].lazytag;
 // left son updating: push down & update segment sum
 segTree[rSon(p)].lazytag += segTree[p].lazytag;
 segTree[rSon(p)].data += (segTree[rSon(p)].rgt - segTree[rSon(p)].lft + 1) * segTree[p].lazytag;
 // self updating
 segTree[p].lazytag = 0;
 }
 void modify(long long p, long long l, long long r, long long val)
 {
 if (segTree[p].lft > r || segTree[p].rgt < l)
 return; // exit because of not inside of the segment
 if (segTree[p].lft >= l && segTree[p].rgt <= r)
 { // all inside the segment, add directly
 segTree[p].data += (segTree[p].rgt - segTree[p].lft + 1) * val;
 segTree[p].lazytag += val;
 return;
 }
 if (segTree[p].lazytag)
 spread(p);
 modify(lSon(p), l, r, val);
 modify(rSon(p), l, r, val);
 segTree[p].data = segTree[lSon(p)].data + segTree[rSon(p)].data;
 }
 long long query(long long p, long long l, long long r)
 {
 if (segTree[p].lft > r || segTree[p].rgt < l)
 return 0; // exit because of not inside of the segment
 if (segTree[p].lft >= l && segTree[p].rgt <= r)
 return segTree[p].data; // all inside the segment, return diretly
 if (segTree[p].lazytag)
 spread(p);
 return query(lSon(p), l, r) + query(rSon(p), l, r);
 }
 int main(int argc, char const *argv[])
 {
 scanf("%lld%lld", &n, &m);
 for (long long i = 1; i <= n; i++)
 scanf("%lld", a + i);
 buildTree(1, 1, n);
 while (m--)
 {
 scanf("%lld%lld%lld", &op, &x, &y);
 if (op & 1)
 {
 scanf("%lld", &k);
 modify(1, x, y, k);
 }
 else
 printf("%lld\n", query(1, x, y));
 }
 return 0;
 }
}; // namespace segmentTreeWithoutEternalizing
int main(int argc, char const *argv[])
{
#ifndef ONLINE_JUDGE
 freopen("_data.in", "r", stdin);
 // freopen("_data.out", "w", stdout);
#endif
 return segmentTreeWithoutEternalizing::main(argc, argv);
}

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
struct SegmentTree {
 vector<long long> tree, lazyAdd, lazyMul;
 int n;
 long long mod;
 SegmentTree(int size, long long mod) : n(size), mod(mod) {
 tree.resize(4 * size, 0);
 lazyAdd.resize(4 * size, 0);
 lazyMul.resize(4 * size, 1);
 }
 void push(int node, int l, int r) {
 if (lazyMul[node] != 1 || lazyAdd[node] != 0) {
 int mid = (l + r) / 2;
 int leftChild = node * 2 + 1;
 int rightChild = node * 2 + 2;
 
 // Apply the multiplication and addition to the left child
 tree[leftChild] = (tree[leftChild] * lazyMul[node] + lazyAdd[node] * (mid - l + 1)) % mod;
 lazyAdd[leftChild] = (lazyAdd[leftChild] * lazyMul[node] + lazyAdd[node]) % mod;
 lazyMul[leftChild] = (lazyMul[leftChild] * lazyMul[node]) % mod;
 
 // Apply the multiplication and addition to the right child
 tree[rightChild] = (tree[rightChild] * lazyMul[node] + lazyAdd[node] * (r - mid)) % mod;
 lazyAdd[rightChild] = (lazyAdd[rightChild] * lazyMul[node] + lazyAdd[node]) % mod;
 lazyMul[rightChild] = (lazyMul[rightChild] * lazyMul[node]) % mod;
 
 // Clear the lazy values for this node
 lazyMul[node] = 1;
 lazyAdd[node] = 0;
 }
 }
 void updateRange(int node, int l, int r, int ul, int ur, long long mul, long long add) {
 if (ul > r || ur < l) return;
 if (ul <= l && r <= ur) {
 tree[node] = (tree[node] * mul + add * (r - l + 1)) % mod;
 lazyAdd[node] = (lazyAdd[node] * mul + add) % mod;
 lazyMul[node] = (lazyMul[node] * mul) % mod;
 return;
 }
 push(node, l, r);
 int mid = (l + r) / 2;
 updateRange(node * 2 + 1, l, mid, ul, ur, mul, add);
 updateRange(node * 2 + 2, mid + 1, r, ul, ur, mul, add);
 tree[node] = (tree[node * 2 + 1] + tree[node * 2 + 2]) % mod;
 }
 long long queryRange(int node, int l, int r, int ql, int qr) {
 if (ql > r || qr < l) return 0;
 if (ql <= l && r <= qr) return tree[node];
 push(node, l, r);
 int mid = (l + r) / 2;
 return (queryRange(node * 2 + 1, l, mid, ql, qr) + queryRange(node * 2 + 2, mid + 1, r, ql, qr)) % mod;
 }
 void updateRange(int l, int r, long long mul, long long add) {
 updateRange(0, 0, n - 1, l, r, mul, add);
 }
 long long queryRange(int l, int r) {
 return queryRange(0, 0, n - 1, l, r);
 }
};
int main() {
 int n, q;
 long long m;
 cin >> n >> q >> m;
 
 vector<int> arr(n);
 for (int i = 0; i < n; ++i) {
 cin >> arr[i];
 }
 SegmentTree segTree(n, m);
 // Initialize the segment tree
 for (int i = 0; i < n; ++i) {
 segTree.updateRange(i, i, 1, arr[i]);
 }
 while (q--) {
 int type;
 cin >> type;
 int x, y;
 long long k;
 if (type == 1) {
 cin >> x >> y >> k;
 segTree.updateRange(x - 1, y - 1, k, 0);
 } else if (type == 2) {
 cin >> x >> y >> k;
 segTree.updateRange(x - 1, y - 1, 1, k);
 } else if (type == 3) {
 cin >> x >> y;
 cout << segTree.queryRange(x - 1, y - 1) << endl;
 }
 }
 return 0;
}

第二个用了STL