首页 > 其他分享 >线段树

线段树

时间：2024-08-28 21:39:54浏览次数：10  
标签：std node int 线段 tr sum ll

线段树

区间加 区间和

区间乘法的懒标记优先级高于加法，且会对加法懒标记造成影响

void push_up(node &u,node &l,node &r) {
	u.sum = l.sum + r.sum; // 
}
void pushup(vector<node> &tr, int u) {
    push_up(tr[u],tr[u<<1],tr[u<<1|1]);
}
void push_down(vector<node> &tr,int u) { // 
	if(tr[u].la != 0) {
		tr[u<<1].la += tr[u].la;
		tr[u<<1|1].la += tr[u].la;
		tr[u<<1].sum += (tr[u<<1].r - tr[u<<1].l + 1) * 1ll *  tr[u].la;
		tr[u<<1|1].sum += (tr[u<<1|1].r - tr[u<<1|1].l + 1) * 1ll *  tr[u].la;
		tr[u].la = 0;
	}
}
void build(vector<node> &tr, int u, int l, int r,vector<int> &a) {
    tr[u].l = l; tr[u].r = r;
    if (l == r) {
    	tr[u] = {l,r,a[l],0}; // 
        return;
    }
    int mid = (l + r) >> 1;
    build(tr,u << 1,l,mid,a);
    build(tr,u << 1 | 1,mid + 1,r,a);
    pushup(tr, u);
}

void modify(vector<node> &tr, int u , int L , int R, int k) {
	int l = tr[u].l, r = tr[u].r;
	if(l >= L && r <= R) { // 目标区间
		tr[u].sum += 1ll * (r - l + 1) * k;
		tr[u].la += k;
		return;
	}
	int mid = (l + r) >> 1;
	push_down(tr,u);
	if(L <= mid) modify(tr,u<<1,L,R,k);
	if(R > mid) modify(tr,u<<1|1,L,R,k);
	pushup(tr,u);
}

node query(vector<node> &tr,int u,int L,int R) {
	if(L <= tr[u].l && tr[u].r <= R) return tr[u];
	int mid = (tr[u].l + tr[u].r) >> 1;
    push_down(tr,u);
	if(R <= mid) return query(tr,u << 1,L,R);
	else if(L > mid) return query(tr,u << 1 | 1,L,R);
	else {
		node p,pl,pr;
		pl = query(tr,u << 1,L,R);
		pr = query(tr,u << 1 | 1,L,R);
		push_up(p,pl,pr);
		return p;
	}
}

区间赋值 等差数列

\(1\ l\ r\ k\) ：表示将下标在 \([l , r]\) 区间内的数字替换成 \([k,k+1,…,k+r-l]\)

\(lazy\) 仅表示一个区间最左侧的值 ，通过\(lazy\) 和区间长度 可以得到 \(sum\)

$sum = (lazy + lazy + (len - 1)) / 2 * len $

$sum = \frac{n(a_{1} + a_{n})}{2} $

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct node{
	int l,r;
	ll sum;
	ll la;
};
void push_up(node &u,node &l,node &r) {
	u.sum = l.sum + r.sum;
}
void pushup(vector<node> &tr, int u) {
    push_up(tr[u],tr[u<<1],tr[u<<1|1]);
}
void push_down(vector<node> &tr,int u) {
	if(tr[u].la != 0) {
		ll len = tr[u<<1].r - tr[u<<1].l + 1;
		tr[u<<1].la = tr[u].la;
		tr[u<<1].sum = (tr[u].la + tr[u].la + len - 1) * len / 2;
		tr[u<<1|1].la = tr[u].la + len;
		ll lgt = tr[u<<1|1].r - tr[u<<1|1].l + 1;
		tr[u<<1|1].sum = (tr[u<<1|1].la + tr[u<<1|1].la + lgt - 1) * lgt / 2;
		tr[u].la = 0;
	}
}
void build(vector<node> &tr, int u, int l, int r,vector<int> &a) {
    tr[u].l = l; tr[u].r = r;
    if (l == r) {
    	tr[u] = {l,r,a[l],0};
        return;
    }
    int mid = (l + r) >> 1;
    build(tr,u << 1,l,mid,a);
    build(tr,u << 1 | 1,mid + 1,r,a);
    pushup(tr, u);
}

void modify(vector<node> &tr, int u , int L , int R, int k) {
	int l = tr[u].l, r = tr[u].r;
	if(l >= L && r <= R) { // 目标区间 L,R
		tr[u].la = k + (l - L);
		tr[u].sum = (tr[u].la + tr[u].la + (r - l) ) * (r - l + 1) / 2;
		return;
	}
	int mid = (l + r) >> 1;
	push_down(tr,u);
	if(L <= mid) modify(tr,u<<1,L,R,k);
	if(R > mid) modify(tr,u<<1|1,L,R,k);
	pushup(tr,u);
}

node query(vector<node> &tr,int u,int L,int R) {
	if(L <= tr[u].l && tr[u].r <= R) return tr[u];
	int mid = (tr[u].l + tr[u].r) >> 1;
    push_down(tr,u);
	if(R <= mid) return query(tr,u << 1,L,R);
	else if(L > mid) return query(tr,u << 1 | 1,L,R);
	else {
		node p,pl,pr;
		pl = query(tr,u << 1,L,R);
		pr = query(tr,u << 1 | 1,L,R);
		push_up(p,pl,pr);
		return p;
	}
}
void solve() {
	int n,q;
	std::cin >> n >> q;
	std::vector<int> a(n+1);
	std::vector<node> tr(n * 4 + 4);
	for(int i = 1; i <= n; i++) std::cin >> a[i];
	build(tr,1,1,n,a);
	while(q --) {
		int op,x,y,k;
		std::cin >> op;
		if(op == 1) {
			std::cin >> x >> y >> k;
			modify(tr,1,x,y,k);
		}
		else {
			std::cin >> x >> y;
			std::cout << query(tr,1,x,y).sum << '\n';
		}
	}
	return;
}
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int _ = 1;
	//std::cin >> _;
	while(_ --) {
		solve();
	}
	return 0;
}

区间gcd

给定一个长度为N的数列A，以及M条指令 (N≤5*10^5, M<=10^5)，每条指令可能是以下两种之一：

“C l r d”，表示把 A[l],A[l+1],…,A[r] 都加上 d。

“Q l r”，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。

首先区间\(gcd\) 具有合并性 \(u.d = gcd(l.d,r.d)\)

gcd区间 

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll gcd(ll a,ll b) {
	return b == 0 ? a : gcd(b,a%b);
}
struct node{
	int l,r;
	ll d;
};
void push_up(node &u,node &l,node &r) {
	u.d = gcd(l.d,r.d);
}
void pushup(vector<node> &tr, int u) {
    push_up(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(vector<node> &tr, int u, int l, int r,vector<int> &a) {
    tr[u].l = l; tr[u].r = r;
    if (l == r) {
    	tr[u] = {l,r,a[l]};
        return;
    }
    int mid = (l + r) >> 1;
    build(tr,u << 1,l,mid,a);
    build(tr,u << 1 | 1,mid + 1,r,a);
    pushup(tr, u);
}

node query(vector<node> &tr,int u,int L,int R) {
	if(L <= tr[u].l && tr[u].r <= R) return tr[u];
	int mid = (tr[u].l + tr[u].r) >> 1;
	if(R <= mid) return query(tr,u << 1,L,R);
	else if(L > mid) return query(tr,u << 1 | 1,L,R);
	else {
		node p,pl,pr;
		pl = query(tr,u << 1,L,R);
		pr = query(tr,u << 1 | 1,L,R);
		push_up(p,pl,pr);
		return p;
	}
}


void solve() {
	int n,q;
	std::cin >> n >> q;
	std::vector<int> a(n+1);
	std::vector<node> tr(n * 4 + 4);
	for(int i = 1; i <= n; i++) std::cin >> a[i];
	build(tr,1,1,n,a);
	while(q --) {
		int x,y;
		std::cin >> x >> y;
		std::cout << query(tr,1,x,y).d << '\n';
	}
	return;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int _ = 1;
	//std::cin >> _;
	while(_ --) {
		solve();
	}
	return 0;
}

但是\(gcd(a_l+v,a_{l+1}+v,...,a_r + v)\) 与 \(gcd(a_l,a_{l+1},...,a_r)\) 无关，

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll gcd(ll a,ll b) {
	return b == 0 ? a : gcd(b,a%b);
}
struct node{
	ll l,r;
	ll sum;
	ll d;
};

void push_up(node &u,node &l,node &r) {
	u.sum = l.sum + r.sum; 
	u.d = gcd(l.d,r.d);
}
void pushup(vector<node> &tr, int u) {
    push_up(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(vector<node> &tr, int u, int l, int r,vector<ll> &a) {
    tr[u].l = l; tr[u].r = r;
    if (l == r) {
    	tr[u] = {l,r,a[l],a[l]};
        return;
    }
    int mid = (l + r) >> 1;
    build(tr,u << 1,l,mid,a);
    build(tr,u << 1 | 1,mid + 1,r,a);
    pushup(tr, u);
}

void modify(vector<node> &tr, int u , int L , int R, ll k) {
	int l = tr[u].l, r = tr[u].r;
	if(l >= L && r <= R) { // 目标区间
		tr[u].sum += k;
		tr[u].d += k;
		return;
	}
	int mid = (l + r) >> 1;
	//push_down(tr,u);
	if(L <= mid) modify(tr,u<<1,L,R,k);
	if(R > mid) modify(tr,u<<1|1,L,R,k);
	pushup(tr,u);
}

node query(vector<node> &tr,int u,int L,int R) {
	if(L <= tr[u].l && tr[u].r <= R) return tr[u];
	int mid = (tr[u].l + tr[u].r) >> 1;
    //push_down(tr,u);
	if(R <= mid) return query(tr,u << 1,L,R);
	else if(L > mid) return query(tr,u << 1 | 1,L,R);
	else {
		node p,pl,pr;
		pl = query(tr,u << 1,L,R);
		pr = query(tr,u << 1 | 1,L,R);
		push_up(p,pl,pr);
		return p;
	}
}
void solve() {
	int n,q;
	std::cin >> n >> q;
	std::vector<ll> a(n+1),b(n+1);
	std::vector<node> tr(n * 3);
	for(int i = 1; i <= n; i++) std::cin >> a[i];
	for(int i = 1; i <= n; i++) {
		b[i] = a[i] - a[i-1];
	}
	build(tr,1,1,n,b);
	while(q --) {
		char op;
		int x,y; ll k;
		std::cin >> op;
		if(op == 'C') {
			std::cin >> x >> y >> k;
			modify(tr,1,x,x,k);
			if(y + 1 <= n) {
				modify(tr,1,y+1,y+1,-k);
			}
		}
		else {
			std::cin >> x >> y;
            ll A1 = 0 , A2 = 0;
            if(x <= n) A1 = query(tr,1,1,x).sum;
            if(x + 1 <= y) A2 = query(tr,1,x+1,y).d;
			std::cout << std::abs( gcd(A1,A2) ) << '\n';
		}
	}
	return;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int _ = 1;
	//std::cin >> _;
	while(_ --) {
		solve();
	}
	return 0;
}

区间最大连续子段和

\(max_{x \leq l \leq r \leq y}({\sum_{r_i=l}^{r}A[i]})\)

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

struct node{
	int l,r;
	int sum;
	int lmx,rmx,mx;
};

void push_up(node &u,node &l,node &r) {
	u.sum = l.sum + r.sum;
	u.lmx = max(l.lmx, l.sum + r.lmx);
	u.rmx = max(r.rmx, r.sum + l.rmx);
	u.mx = max({l.mx,r.mx,l.rmx + r.lmx});
}
void pushup(vector<node> &tr, int u) {
    push_up(tr[u],tr[u<<1],tr[u<<1|1]);
}

void build(vector<node> &tr, int u, int l, int r,vector<int> &a) {
    tr[u].l = l; tr[u].r = r;
    if (l == r) {
    	tr[u] = {l,r,a[l],a[l],a[l],a[l]};
        return;
    }
    int mid = (l + r) >> 1;
    build(tr,u << 1,l,mid,a);
    build(tr,u << 1 | 1,mid + 1,r,a);
    pushup(tr, u);
}

void modify(vector<node> &tr, int u , int L , int R, int  k) {
	int l = tr[u].l, r = tr[u].r;
	if(l >= L && r <= R) { // 目标区间
		tr[u].sum = k;
		tr[u].lmx = k;
		tr[u].rmx = k;
		tr[u].mx = k;
		return;
	}
	int mid = (l + r) >> 1;
	//push_down(tr,u);
	if(L <= mid) modify(tr,u<<1,L,R,k);
	if(R > mid) modify(tr,u<<1|1,L,R,k);
	pushup(tr,u);
}

node query(vector<node> &tr,int u,int L,int R) {
	if(L <= tr[u].l && tr[u].r <= R) return tr[u];
	int mid = (tr[u].l + tr[u].r) >> 1;
    //push_down(tr,u);
	if(R <= mid) return query(tr,u << 1,L,R);
	else if(L > mid) return query(tr,u << 1 | 1,L,R);
	else {
		node p,pl,pr;
		pl = query(tr,u << 1,L,R);
		pr = query(tr,u << 1 | 1,L,R);
		push_up(p,pl,pr);
		return p;
	}
}
void solve() {
	int n,q;
	std::cin >> n >> q;
	std::vector<int> a(n+1);
	std::vector<node> tr(n * 4 + 4);
	for(int i = 1; i <= n; i++) std::cin >> a[i];
	build(tr,1,1,n,a);
	while(q --) {
		int op,x,y; int k;
		std::cin >> op;
		if(op == 1) {
			std::cin >> x >> y;
            if(x > y) swap(x,y);
			std::cout << query(tr,1,x,y).mx << '\n';
		}
		else {
			std::cin >> x >> k;
			modify(tr,1,x,x,k);
		}
	}
	return;
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int _ = 1;
	//std::cin >> _;
	while(_ --) {
		solve();
	}
	return 0;
}

标签：std,node,int,线段,tr,sum,ll
From： https://www.cnblogs.com/Elgina/p/18385565

相关文章

  • 【数据结构】【模板】李超线段树
    李超线段树定义可以看看洛谷的模板题目：作用优化动态规划，如果可以将一个动态规划的转移式子转化为\(y=kx+b\)的形式，那么我们可以边转移边将\(y=kx+b\)这条线段放入李超线段树，然后在下次转移时，直接调用下次计算出来的\(x\)位置上的最大值或最小值。（结合题目理解......
  • Luogu P4588 数学运算 题解 [ 绿 ] [ 线段树 ]
    LuoguP4588数学运算。虽然是一个很典的题，但里面的思想还是比较值得记录的。假做法一开始看到此题还以为是乘法逆元的模板题，但看到\(m\)与\(M\)不互质，就知道这种做法是假的了。注意exgcd虽然能求模数为合数的逆元，但是要是两数不互质就什么算法都搞不了了。因此，本题不能......
  • 线段树模版：从入门到入坟
    线段树模版：从入门到入坟线段树——单点修改1.求区间最值#include<bits/stdc++.h>#defineintlonglongusingnamespacestd;constintN=200010;typedeflonglongll;structnode{ intminx; intl,r;}tr[N*4];inta[N];voidupdate(intp){ tr[p].minx=min(tr[......
  • 牛客周赛 Round 57 D-小红的线段（贪心）
     示例1输入2-1200011011输出112N34Y说明连接第一个点和第二个点，和直线没有交点。连接第三个点和第四个点，和直线有交点。 贪心策略：把点集分为三部分，直线上方m1、直线下方m2以及在直线上m3，我们可以发现：m1中的点和m2中的任意点相连都能通过直线；m3......
  • 区间k小值（可持久化线段树）
    题目描述给定一个序列\(a_1,a_2,\dots,a_n\)，\(m\)次操作，每次给定\(l,r,k\)，问\(a_l,a_{l+1},\dots,a_r\)中第\(k\)小的值。输入第一行一个正整数\(T(1\leqT\leq3)\)，表示测试数据的数量。每组数据第一行\(n,m(1\leqn,m\leq100000)\)。第二行\(n\)个正整数\(a_1,a_2,\dots,a......
  • 线段树（3）——区间操作叠加
    如果我既有区间乘法又有区间加法，我应该怎么办呢？这时候需要写两个标记。假设只写一个标记。标记加法：此时对于乘法操作，因为是将\(t_i+lazy_i\)乘以\(x\)，这样子显然一个懒惰标记做不到。标记乘法：那我加法咋办？那两个标记怎么用呢？首先假设加法标记为\(lazy\)，乘法标记为\(multi......
  • 线段树维护单调栈——区间查询版本 & 维护递减序列
    这次算是完全搞懂了吧（）（）（#include<bits/stdc++.h>#defineraedread#definecaclcalc#definepbpush_back#definepiipair<int,int>#defineintlonglong#definefifirst#definesesecond#definelsp<<1#definersp<<1|1usingn......
  • 线段树（2）——懒惰标记Lazy Tag（单运算）及例题
    上一篇文章我们讲了线段树的最基本的操作。如果有一种操作叫做区间加法呢？这个时候显然可以依次单点修改，但是时间复杂度太高了。所以可以考虑优化，由于思考过程可能很长，此处直接引入懒惰标记。懒惰标记就是在对一颗树的所有节点进行某种统一操作时，只对根节点做一个标记表示它的子树......
  • 线段树进阶
    线段树进阶目录线段树进阶线段树+贪心/线段树+排序例题:1.洛谷P1607FairShuttleG2.洛谷P1937BarnAllocationG3.洛谷P1972HH的项链线段树+双指针例题:1.洛谷P1712区间线段树+多个标记维护例题:1.洛谷P2572序列操作线段树+二分例题:1.洛谷P4344脑洞治疗仪2.洛谷P2824排......
  • 线段树 Ⅰ
    前言线段树用于维护数列区间上的值，可以在\(O(\logn)\)的时间复杂度内实现单点，区间修改及查询。并且所有满足结合律的运算都可以用线段树进行加速。基本操作建树给你长度为\(n\)的正整数序列\(A\)，要你实现单点修改与区间查询。（加和）这就是线段树的基本题目。线段树，字面上......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99