Exile_Code @ 2023-09-09 23:26:10
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
using namespace std;
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <list>
#include <string>
#include <cmath>
#include <bitset>
#include<stack>
using namespace std;
using ll = long long;
#define LF(x) fixed << setprecision(x)
typedef pair<int, int> pii;
#define endl "\n"
int n, w[100];
struct node { int l, r, sum, add; }tr[4 * 100];
//线段树
class Segment_tree {
/*
叶子节点储存元素本身,非叶子节点存储统计值,用来维护区间和,区间最值,区间GCD
父节点的编号是p,左孩子的编号是2p,右孩子的编号是2p+1
*/
private:
#define lc p<<1
#define rc p<<1|1
public:
//建树
void build(int p, int l, int r) {
tr[p] = { l,r,w[l] };//这个操作对于非叶子结点是没有意义的,因为在最后一步会进行更新
if (r == l)return;
int m = l + r >> 1;
build(lc, l, m);
build(rc, m + 1, r);//p<<2一定是一个偶数,偶数的末位是0,所以按位或1,相当于+1
tr[p].sum = tr[lc].sum + tr[rc].sum;
}
//区间查询,拆分拼凑,如果查询区间完全覆盖掉当前的节点区间,就立刻返回当前的区间值 On
int query(int p, int x, int y) {
if (x <= tr[p].l && tr[p].r <= y)
return tr[p].sum;
int m = tr[p].l + tr[p].r >> 1;
pushdown(p);
int sum = 0;
if (x <= m) sum += query(lc, x, y);
if (y > m) sum += query(rc, x, y);
return sum;
}
//向上更新
void pushup(int p) {
tr[p].sum = tr[lc].sum + tr[rc].sum;
}
//下传懒标记
void pushdown(int p) {
if (tr[p].add) {
tr[lc].sum += tr[p].add * (tr[lc].r - tr[lc].l + 1);
tr[rc].sum += tr[p].add * (tr[rc].r - tr[rc].l + 1);
tr[lc].add += tr[p].add;
tr[rc].add += tr[p].add;
tr[p].add = 0;
}
}
//区间修改
void update(int p, int x, int y, int k) {
if (x <= tr[p].l && tr[p].r <= y) {//覆盖则修改
tr[p].sum += (tr[p].r - tr[p].l + 1) * k;//宽度*k
tr[p].add += k;
return;
}
int m = tr[p].l + tr[p].r >> 1;
pushdown(p);
if (x <= m) update(lc, x, y, k);
if (y > m) update(rc, x, y, k);//不取等是因为,等于的情况已经在上一句修改了
pushup(p);
}//懒惰修改,当完全覆盖时就打上懒标记,下次需要的时候再下传懒标记 Ologn
//点修改
void update(int p, int x, int k) {
if (tr[p].l == x && tr[p].r == x) {
tr[p].sum += k;
return;
}
int m = tr[p].l + tr[p].r >> 1;//判断这个点在那个子树上面
if (x <= m)update(lc, x, k);
else update(rc, x, k);
tr[p].sum = tr[lc].sum + tr[rc].sum;
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m; cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> w[i];
Segment_tree s;
s.build(1,1,n);
for (int i = 0; i < m; i++) {
int q; cin >> q;
if (q == 1) {
int a, b,k; cin >> a >> b>>k;
s.update(1, a, b, k);
}
else {
int a, b; cin >> a >> b;
cout << s.query(1, a, b) << endl;
}
}
return 0;
}
by __HHX__ @ 2023-09-09 23:43:01
典,注意数据范围(不是线段树)
by __HHX__ @ 2023-09-09 23:47:22
建议看一下
对于
和
保证任意时刻数列中所有元素的绝对值之和