Knowledge Arrangement of Line Segment Tree Template (Lazy Markers, Structures)

A Set of Line Segment Tree Templates Suitable for Your Style

After a day and a half of suffering, the beginning of headache is not possible, I really can not understand, until now, the line section tree finally seems to be in the hole, looking for a lot of information on the Internet, and finally able to write a template suited to my style combined with others. Now let's record some of my understandings and code, and come back to see it later when it's ambiguous. Recommended Video: The idea of lighting lanterns on station b is easy to understand, but the code is difficult to imitate, and the code of SWPU-ACM is easy to imitate. There are also many detailed explanations on the powerful CSDN.
My code mainly uses a structure to represent the tree. I think using the structure can better show the characteristics of the tree and the content of each node. There are many test screenshots saved in the process of writing, but now I am too lazy to upload... I add some comments next to the code.
The following functions include:

void build(int rt, int l, int r)
rt represents the root node to be created each time, and l and r represent the left and right endpoint values on the tree
 void update(int rt, int p, int val)
rt is still the root node of the tree, p is the location to be modified, and val is the new value.
void update(int rt, int l, int r, int c) (interval modification)
The function is to add c to each value in the interval from l to r.
int query(int rt, int p) (single point query)
Query the value of point p
 int query(int rt, int l, int r) (interval query)
To query the information in the interval from l to r, you can query sum, max, min.···
void down(int rt) [lazy tag download]
When the lazy label (interval modification) is used and the interval or single-point query is performed again, the lazy label download is required.

The line segment tree template is as follows (lazy marker):

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define lson  rt<<1, l, mid
#define rson  rt<<1|1, mid+1, r 
using namespace std;
const int maxn = 1e5;
int a[maxn];
struct node{
	int l, r;
	int sum;
	int lazy;
int n, m;
void up(int rt){
	tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
void down(int rt){
		tree[rt<<1].lazy = tree[rt].lazy;
		tree[rt<<1|1].lazy = tree[rt].lazy;
		tree[rt<<1].sum = tree[rt].lazy * (tree[rt<<1].r-tree[rt<<1].l+1);
		tree[rt<<1|1].sum = tree[rt].lazy * (tree[rt<<1|1].r-tree[rt<<1|1].l+1);
		tree[rt].lazy = 0;
void build(int rt, int l, int r){
	tree[rt].l = l, tree[rt].r = r;
	tree[rt].lazy = 0;
	// If there is only one value in the interval recorded by the current node, it means that the leaf node has been found and assigned directly.
	// Otherwise, the left and right subtrees are constructed recursively, and the current node is assigned a value at the end of backtracking.
	if(l == r){
		tree[rt].sum = a[l];
		return ;
	int mid = (l + r) >> 1;
	build(rt<<1, l, mid);
	build(rt<<1|1, mid+1, r);
	tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
void update(int rt, int p, int val){
	// Single point modification 
	// This if statement is used to determine whether the leaf node is reached or not. 
	if(tree[rt].l == tree[rt].r){
		tree[rt].sum = val;
		return ;
	int mid = (tree[rt].l + tree[rt].r) >> 1;
	if(p <= mid)	update(rt<<1, p, val);
	else	 		update(rt<<1|1, p, val);
	tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
void update(int rt, int l, int r, int c){
	// Modify the interval and add c at the same time
	if(tree[rt].l >= l && tree[rt].r <= r){
		tree[rt].lazy = c;		// Record this tag
		tree[rt].sum += c * (tree[rt].r - tree[rt].l + 1);
		return ; 
	int mid = (tree[rt].l + tree[rt].r) >> 1;
	if(mid >= r)		update(rt<<1, l, r, c);
	else if(mid < l)	update(rt<<1|1, l, r, c);
		update(rt<<1, l, mid, c);
		update(rt<<1|1, mid+1, r, c);
	tree[rt].sum = tree[rt<<1].sum + tree[rt<<1|1].sum;
int query(int rt, int p){
	// Single-point query
	if(tree[rt].l == tree[rt].r)	
		return tree[rt].sum;
	int mid = (tree[rt].l + tree[rt].r) >> 1; 
//	down(rt);
	int ans;
	if(p <= mid)	ans = query(rt<<1, p);
	else	ans = query(rt<<1|1, p);
	return ans;
int query(int rt, int l, int r){
	// Interval query 
	if(tree[rt].l >= l && tree[rt].r <= r)
		return tree[rt].sum;
	down(rt);		// Use lazy arrays 
	int mid = (tree[rt].l + tree[rt].r) >> 1; 
	if(r <= mid)		return query(rt<<1, l, r);
	else if(mid < l)	return query(rt<<1|1, l, r);
		return query(rt<<1, l, mid) + query(rt<<1|1, mid+1, r);
int main(){
	cin >> n ;
	for(int i = 1; i <= n; i++)	
		cin >> a[i];
	build(1, 1, n);
	for(int i = 1; i <= 15; i++)	
		cout << tree[i].sum <<" "<< tree[i].lazy << endl;
		cout << query(1, 3, 6) << endl;		 
	return 0;

Added by mmitdnn on Sat, 17 Aug 2019 10:33:51 +0300