线段树提高（1）

• 核心操作
• 原理
• 基本操作
• • build
  • query
  • 证明次数在logn内
• 单点修改
• 例题
• • 求最大值
  • 最长连续子区间和
  • 区间修改，区间查询，问区间gcd

1.pushup 从子节点往父节点传消息
2.pushdown 从父节点到子节点，也叫懒标记

凡是只会涉及到只会修改单点的，这样的操作都是不需要用懒标记的，他们本身就可以做到logn的时间复杂度。凡是涉及到区间的，修改某一个区间的，这样的某一个操作都需要懒标记，否则时间复杂度会退化

线段树debug一般先通读一遍

长相如图，可见，除了最后一层，这是一个满二叉树，跟堆一样，所以我们也就可以用一维数组来存线段树

节点个数，满二叉树最后一层最多有n个点，满二叉树的性质，最后一层n个点，总共2n-1个点，然后树状数组的最后一层又最多是满二叉树最后一层的两倍，就是2n-1 + 2n = 4n - 1

如果感觉第一种不好像的话，就举个例，比如，求区间最大值，当前区间被包含在所求区间内，则说明，这个区间的最大值一定小于等于最终结果，当前这个区间的最大值就被返回去跟目前的答案比较一下，如果是比当前结果大，就更新一下答案

第三种情况不存在

如果比如在1-10内查询5-9

就需要查询这八个区间

自己看视频，20min左右，提高课

第二种情况的分类讨论

最多有4logn的点的数量，听Y总讲能明白，也就是分裂开最多2条链，每个链最多两个点（递归左边和右边）

从上往下递归就可以，必然会递归到某个叶节点

很大一部分内容不在赘述，在这里有

但是要记录的区间性质，这个首先就是要看能不能直接由两个区间的属性算出来，如果能，那就直接算，如果不能就考虑要不要加一些其他属性

这里

#include
using namespace std;

#define int long long

const int N = 2e5+10;

int m, p;
struct Node
{
    int l, r;
    int v;  // 区间[l, r]中的最大值
}tr[N * 4];

void pushup(int u)  // 由子节点的信息，来计算父节点的信息
{
    tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}

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

int query(int u, int l, int r)//u是我们查询的当前线段树的端点
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u].v;   // 树中节点，已经被完全包含在[l, r]中了

    int mid = tr[u].l + tr[u].r >> 1;//当前树中区间的端点的中点
    int v = 0;
    if (l <= mid) v = query(u << 1, l, r);//看看和左边有没有交集
    if (r > mid) v = max(v, query(u << 1 | 1, l, r));//和右边有没有交集
    //这里是r > mid，因为我们划分区间的时候，是把区间划分成了[l, mid],  [mid+1, r]，所以是大于

    return v;
}

void modify(int u, int x, int v)//每次修改某个点，把它修改成v
{
    if (tr[u].l == x && tr[u].r == x) tr[u].v = v;//当前已经是叶子节点
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);//更新最大值信息，更新父节点信息
    }
}

signed main()
{
	int n=0, last =0;//n是当前数据的个数，last表示上一次查询的答案，就是题目中的a
	
	scanf("%lld%lld", &m, &p);
	build(1, 1, m);//提前开好m个空，最多有m个
	char op[2];
	int l, t;
	while(m--)
	{
		scanf("%s", op);
		if(op[0] == 'Q')
		{
			scanf("%lld", &l);
			last = query(1, n-l+1, n);
			cout<
			scanf("%lld", &t);
			modify(1, n+1, (last + t)%p);
			n++;
		}
	}
	return 0;
}

你能回答这些问题吗

先考虑把答案维护出来，然后再考虑用当前的信息能不能把答案算出来，如果不能就需要加一些额外信息，加完之后还要再想一想，加了额外的信息能不能维护出来，如果不够还要再加，直到能把所有的信息全部算出来为止

#include
using namespace std;

#define int long long

const int N = 5e5 + 10;

int n, m;
int w[N];
struct node
{
    int l, r;
    int sum;  // 区间[l, r]中的最大子段和
	int lsum;//最大前缀和
	int rsum;//最大后缀和
	int tsum;//区间和
	//横跨左右区间的最大子段和一定是左子区间的最大后缀和右子区间的最大前缀
	//还有一种情况就是把一边完全包括然后横跨到另一个了
}tr[N * 4];

void pushup(node &u, node &l, node &r)
{
	u.sum = l.sum + r.sum;
	u.lsum = max(l.lsum, l.sum + r.lsum);
	u.rsum = max(r.rsum, r.sum + l.rsum);
	u.tsum = max(max(l.tsum, r.tsum), l.rsum + r.lsum);
	
}
void pushup(int u)  // 由子节点的信息，来计算父节点的信息
{
   pushup(tr[u], tr[u<<1], tr[u<<1|1]);
}

void build(int u, int l, int r)
{
    tr[u] = {l, r};
    if (l == r) 
	{
		tr[u].sum = w[r];
		tr[u].lsum = w[r];
		tr[u].rsum = w[r];
		tr[u].tsum = w[r];
		return;
	}
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

node query(int u, int l, int r)//查询的时候，只要有跨左右两边的，就需要返回四个信息，为了方便，就返回一个节点
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];   // 树中节点，已经被完全包含在[l, r]中了
	
    int mid = tr[u].l + tr[u].r >> 1;
    if (r <= mid) return query(u << 1, l, r);
    else if (l > mid) return query(u << 1 | 1, l, r);
    else
    {
        auto left = query(u << 1, l, r);
        auto right = query(u << 1 | 1, l, r);
        node res;
        pushup(res, left, right);
        return res;
    }
}

void modify(int u, int x, int v)
{
    if (tr[u].l == x && tr[u].r == x) 
	{
		
		tr[u].sum = v;
		tr[u].lsum = v;
		tr[u].rsum = v;
		tr[u].tsum = v;
	}
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
    
}

signed main()
{
	scanf("%lld%lld", &n, &m);
	for(int i=1;i<=n;i++) scanf("%lld", &w[i]);
	build(1, 1, n);
//	char op[2];
	int k, x, y;
	while(m--)
	{
		scanf("%lld", &k);
		if(k==1)
		{
			scanf("%lld%lld", &x, &y);
			if(x>y) swap(x, y);
			cout<
			scanf("%lld%lld", &x, &y);
			modify(1, x, y);
		}
	}
	return 0;
}

区间最大公约数

首先证明一下，左边的跟右边的相等。
假设左边的最大公约数是d，则，d能整除a1…an，那么d也一定能整除右边所有数，所以d也是右边的公约数，也就是右边大于等于左边，同理，左边也大于等于右边，综上，左右两边的最大公约数相等

也就是gcd(x, y, z) = gcd(x, y - x, z - y)

#include 
#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 500010;

int n, m;
LL w[N];
struct Node
{
    int l, r;
    LL sum, d;
}tr[N * 4];

LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}

void pushup(Node &u, Node &l, Node &r)
{
    u.sum = l.sum + r.sum;
    u.d = gcd(l.d, r.d);
}

void pushup(int u)
{
    pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
}

void build(int u, int l, int r)
{
    if (l == r)
    {
        LL b = w[r] - w[r - 1];
        tr[u] = {l, r, b, b};
    }
    else
    {
        tr[u].l = l, tr[u].r = r;
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

void modify(int u, int x, LL v)
{
    if (tr[u].l == x && tr[u].r == x)
    {
        LL b = tr[u].sum + v;
        tr[u] = {x, x, b, b};
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (x <= mid) modify(u << 1, x, v);
        else modify(u << 1 | 1, x, v);
        pushup(u);
    }
}

Node query(int u, int l, int r)
{
    if (tr[u].l >= l && tr[u].r <= r) return tr[u];
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if (r <= mid) return query(u << 1, l, r);
        else if (l > mid) return query(u << 1 | 1, l, r);
        else
        {
            auto left = query(u << 1, l, r);
            auto right = query(u << 1 | 1, l, r);
            Node res;
            pushup(res, left, right);
            return res;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &w[i]);
    build(1, 1, n);

    int l, r;
    LL d;
    char op[2];
    while (m -- )
    {
        scanf("%s%d%d", op, &l, &r);
        if (*op == 'Q')
        {
            auto left = query(1, 1, l);
            Node right({0, 0, 0, 0});
            if (l + 1 <= r) right = query(1, l + 1, r);
            printf("%lldn", abs(gcd(left.sum, right.d)));//如果l=rgcd(sum, 0)就是sum
        }
        else
        {
            scanf("%lld", &d);
            modify(1, l, d);
            if (r + 1 <= n) modify(1, r + 1, -d);//如果比n大的话，就不需要修改了，说明加的区间一直到最后一个
        }
    }

    return 0;
}