计科余定成

用户名：dotcpp0598358

访问量：15777

签　名：

孙蕾，我好喜欢你啊，为了你我要把键盘敲烂!!!

等　　级
排　　名	41
经　　验	13043
参赛次数	1
文章发表	69
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

我是余定成

TA的其他文章

图的遍历-DFS
浏览：56

求具有abcd=(ab+cd)2性质的四位数
浏览：73

[NOIP2004]合并果子
浏览：89

你可能喜欢

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

贴一个线段树的基础模板

　　作者: 计科余定成　　　　发表时间：2023-03-09 19:49:54 浏览：39　|　评论：0　

自用
```cpp
#define ll long long
const int N = 1e5 + 5;
ll a[N];
class S_tree {
	private:
		// size 表示线段树的结点数，t 和 lazy 分别为值和懒标记数组
		int size;
		vector<ll> t;
		vector<ll> lazy;
		// 左右儿子的计算
		inline int ls(int p) {
			return p << 1;
		}
		inline int rs(int p) {
			return p << 1 | 1;
		}
		// 维护区间和的方法
		inline void pushup_sum(int p) {
			t[p] = t[ls(p)] + t[rs(p)];
		}
		// 维护区间最大值的方法
		inline void pushup_max(int p) {
			t[p] = max(t[ls(p)], t[rs(p)]);
		}
		// 维护区间最小值的方法
		inline void pushup_min(int p) {
			t[p] = min(t[ls(p)], t[rs(p)]);
		}
		// 区间修改的前置函数
		inline void f_sum(ll p, ll l, ll r, ll k) {
			lazy[p] += +k;
			t[p] += k * (r - l + 1);
		}
		// 下传懒标记的方法
		void pushdown(ll p, ll l, ll r) {
			ll mid = (l + r) >> 1;
			f_sum(ls(p), l, mid, lazy[p]);
			f_sum(rs(p), mid + 1, r, lazy[p]);
			lazy[p] = 0;
		}
	public:
		//构造函数
		S_tree(int n) {
			this->size = n;
			t.resize(size << 2);
			lazy.resize(size << 2);
		}
		//区间和相关操作
		void build_sum(ll p, ll l, ll r) {
			if (l == r) t[p] = a[l];
			ll mid = (l + r) >> 1;
			build_sum(ls(p), l, mid);
			build_sum(rs(p), mid + 1, r);
			pushup_sum(p);
		}
		void update_sum(ll nl, ll nr, ll l, ll r, ll p, ll k) {
			if (nl <= l && r <= nr) {
				t[p] += k * (r - l + 1);
				lazy[p] += k;
				return;
			}
			pushdown(p, l, r);
			int mid = (l + r) >> 1;
			if (nl <= mid) update_sum(nl, nr, l, mid, ls(p), k);
			if (nr > mid) update_sum(nl, nr, mid + 1, r, rs(p), k);
			pushup_sum(p);
		}
		ll query_sum(ll nl, ll nr, ll l, ll r, ll p) {
			ll sum = 0;
			if (nl <= l && nr >= r) return t[p];
			ll mid = (l + r) >> 1;
			if (nl <= mid) sum += query_sum(nl, nr, l, mid, ls(p));
			if (nr > mid) sum += query_sum(nl, nr, mid + 1, r, rs(p));
			return sum;
		}
		//区间最大值相关操作
		void build_max(ll p, ll l, ll r) {
			if (l == r) t[p] = a[l];
			else {
				ll mid = (l + r) >> 1;
				build_max(ls(p), l, mid);
				build_max(rs(p), mid + 1, r);
				pushup_max(p);
			}
		}
		void update_max(ll nl, ll nr, ll l, ll r, ll p, ll k) {
			if (nl <= l && r <= nr) {
				t[p] += k * (r - l + 1);
				lazy[p] += k;
				return;
			}
			pushdown(p, l, r);
			int mid = (l + r) >> 1;
			if (nl <= mid) update_max(nl, nr, l, mid, ls(p), k);
			if (nr > mid) update_max(nl, nr, mid + 1, r, rs(p), k);
			pushup_max(p);
		}
		ll query_max(ll nl, ll nr, ll l, ll r, ll p) {
			if (r < nl || l > nr) return -999999999;
			if (nl <= l && r <= nr) return t[p];
			else {
				int mid = (l + r) >> 1;
				ll ml = query_max(nl, nr, l, mid, ls(p));
				ll mr = query_max(nl, nr, mid + 1, r, rs(p));
				return max(ml, mr);
			}
		}
		//区间最小值相关操作
		void build_min(ll p, ll l, ll r) {
			if (l == r) t[p] = a[l];
			else {
				ll mid = (l + r) >> 1;
				build_min(ls(p), l, mid);
				build_min(rs(p), mid + 1, r);
				pushup_min(p);
			}
		}
		void update_min(ll nl, ll nr, ll l, ll r, ll p, ll k) {
			if (nl <= l && r <= nr) {
				t[p] += k * (r - l + 1);
				lazy[p] += k;
				return;
			}
			pushdown(p, l, r);
			int mid = (l + r) >> 1;
			if (nl <= mid) update_min(nl, nr, l, mid, ls(p), k);
			if (nr > mid) update_min(nl, nr, mid + 1, r, rs(p), k);
			pushup_min(p);
		}
		ll query_min(ll nl, ll nr, ll l, ll r, ll p) {
			if (r < nl || l > nr) return 999999999;
			if (nl <= l && r <= nr) return t[p];
			else {
				int mid = (l + r) >> 1;
				ll ml = query_min(nl, nr, l, mid, ls(p));
				ll mr = query_min(nl, nr, mid + 1, r, rs(p));
				return min(ml, mr);
			}
		}
};
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

剔除相关数（C语言代码）

贴一个线段树的基础模板

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C二级辅导-统计字符（C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-排序问题<1> （C++代码）

C语言训练-最大数问题（C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言训练-自由落体问题（C语言代码）

IP判断（C语言描述，蓝桥杯）

DNA （C语言代码）

sizeof的大作用（C语言代码）

计科余定成

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.6 （C语言代码）

C语言程序设计教程（第三版）课后习题6.9 （C语言代码）

C语言程序设计教程（第三版）课后习题6.6 （C++代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

剔除相关数 （C语言代码）

贴一个线段树的基础模板

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C二级辅导-统计字符 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言训练-排序问题<1> （C++代码）

C语言训练-最大数问题 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

C语言训练-自由落体问题 （C语言代码）

IP判断 （C语言描述，蓝桥杯）

DNA （C语言代码）

sizeof的大作用 （C语言代码）

剔除相关数（C语言代码）

　　评论区

C二级辅导-统计字符（C语言代码）

C语言训练-最大数问题（C语言代码）

C语言训练-自由落体问题（C语言代码）

IP判断（C语言描述，蓝桥杯）

sizeof的大作用（C语言代码）