首页 > 其他分享 >如何用线段树维护一些数学公式

如何用线段树维护一些数学公式

时间:2023-01-09 09:23:16浏览次数:40  
标签:opt 数学公式 int 线段 cin 维护 ll 等差数列 mod

1. 维护等差数列

例1:洛谷 P1438 无聊的数列(插入等差数列,单点查询)

这题有两个做法,第一个做法是用线段树维护等差数列,不过这里不多赘述,在下一个例子再详细介绍;第二个做法是用线段树维护差分数组,把单点查询转化为查询前缀和。

#include <bits/stdc++.h>

using namespace std;
const int N = 100005;
typedef long long ll;
int n, m;
int a[N];

struct Seg_Tree {
    struct node {
        int l, r;
        ll s, tag;
    } seg[N * 4];
    void pushup(int k)
    {
        seg[k].s = seg[k << 1].s + seg[k << 1 | 1].s;
    }
    void set_tag(int k, ll add)
    {
        int len = seg[k].r - seg[k].l + 1;
        seg[k].s += 1ll * add * len;
        seg[k].tag += add;
    }
    void pushdown(int k)
    {
        if(seg[k].tag != 0)
        {
            set_tag(k << 1, seg[k].tag);
            set_tag(k << 1 | 1, seg[k].tag);
            seg[k].tag = 0;
        }
    }
    void build(int k, int l, int r)
    {
        seg[k] = {l, r, 0, 0};
        if(l == r) {
            seg[k].s = a[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
        pushup(k);
    }
    void modify(int k, int ql, int qr, ll v)
    {
        int l = seg[k].l, r = seg[k].r;
        if(ql <= l && r <= qr)
        {
            set_tag(k, v);
            return;
        }
        pushdown(k);
        int mid = (l + r) >> 1;
        if(ql <= mid)
            modify(k << 1, l, mid, ql, qr, v);
        if(mid < qr)
            modify(k << 1 | 1, mid + 1, r, ql, qr, v);
        pushup(k);
    }
    ll query(int k, int ql, int qr)
    {
		int l = seg[k].l, r = seg[k].r;
        if(ql <= l && r <= qr)
            return seg[k].s;
        pushdown(k);
        int mid = (l + r) >> 1;
        ll res = 0;
        if(ql <= mid)
            res += query(k << 1, l, mid, ql, qr);
        if(mid < qr)
            res += query(k << 1 | 1, mid + 1, r, ql, qr);
        return res;
    }
};
Seg_Tree T1;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    for(int i = n; i >= 1; i --)
        a[i] = a[i] - a[i - 1];
    T1.build(1, 1, n);
    
    while(m --)
    {
        int opt;
        cin >> opt;
        if(opt == 1)
        {
            int l, r, k, d;
            cin >> l >> r >> k >> d;
            T1.modify(1, l, l, k);
            if(l != r)
                T1.modify(1, l + 1, r, d);
            if(r + 1 <= n)
                T1.modify(1, r + 1, r + 1, (l - r) * d - k);
        }
        else 
        {
            int p;
            cin >> p;
            cout << T1.query(1, 1, p) << '\n';
        }
    }
}

例2:牛牛的等差数列(插入等差数列,区间查询)

在这道题就详细地谈一下是怎么用线段树来维护等差数列的。

维护线段的区间和,懒标记分别为首项 \(x\) 和公差 \(d\) ,然后根据传到该区间的的首项和公差,再结合区间长度,通过等差数列求和公式计算出等差数列的和

又因为是区间修改,所以我们是需要懒标记的。懒标记中需要含有我们计算和的关键:首项和公差。我们可以思考如何对一段区间进行修改:若整个区间都在 \(mid\) 的左边或者整个区间都在 \(mid\) 的右边,那么首项和公差直接累加上去就行了;若区间被 \(mid\) 分割为两段,把等差数列分成两段,当然右边的首项跟左边的首项是不一样的。

那我们下传懒标记的时候,把懒标记的贡献加到区间和里,然后再累加懒标记。

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int N = 200005;
const ll mod = 111546435, inv2 = 55773218; //mod是lcm(3,25),inv2是2在mod下逆元
int n, q;
ll a[N];


ll calc(ll k, ll d, ll len)
{
    return (1ll * len * k % mod + len * (len - 1) % mod * d % mod * inv2 % mod) % mod;
}


struct Seg_tree {
    struct node {
        int l, r;
        ll v;
        ll kk, d; //首项,公差
    } seg[N << 2];
    void pushup(int k)
    {
        seg[k].v = (seg[k << 1].v + seg[k << 1 | 1].v) % mod;
    }
    void build(int k, int l, int r)
    {
        seg[k] = {l, r, 0, 0, 0};
        if(l == r) {
            seg[k].v = a[l] % mod;
            return;
        }
        int mid = (l + r) >> 1; 
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
        pushup(k);
    }
    void pushdown(int k)
    {
        auto &l = seg[k << 1], &r = seg[k << 1 | 1];
        auto &kk = seg[k].kk, &d = seg[k].d;
        if(kk && d)
        {
            ll lenl = (l.r - l.l + 1), lenr = (r.r - r.l + 1);
            (l.kk += kk) %= mod;
            (l.d += d) %= mod;
            (l.v += calc(kk, d, lenl)) %= mod;

            ll kk2 = (kk + d * lenl % mod) % mod;
            (r.kk += kk2) %= mod;
            (r.d += d) %= mod;
            (r.v += calc(kk2, d, lenr)) %= mod;

            kk = d = 0;
        }
    }
    void modify(int k, int ql, int qr, ll kk, ll d) 
    {
        int l = seg[k].l, r = seg[k].r;
        if(ql <= l && r <= qr) {
            (seg[k].v += calc(kk, d, 1ll * (r - l + 1))) %= mod;
            (seg[k].kk += kk) %= mod;
            (seg[k].d += d) %= mod;
            return;
        }
        pushdown(k);
        int mid = (l + r) >> 1;
        if(qr <= mid)
            modify(k << 1, ql, qr, kk, d);
        else if(ql > mid)
            modify(k << 1 | 1, ql, qr, kk, d);
        else
        {
            modify(k << 1, ql, mid, kk, d);
            (kk += (d * 1ll * (mid - ql + 1) % mod)) %= mod;
            modify(k << 1 | 1, mid + 1, qr, kk, d);
        }
        pushup(k);
    }
    ll query(int k, int ql, int qr)
    {
        int l = seg[k].l, r = seg[k].r;
        if(ql <= l && r <= qr)
            return seg[k].v;
        pushdown(k);
        int mid = (l + r) >> 1;
        ll res = 0;
        if(ql <= mid)
            res += query(k << 1, ql, qr), res %= mod;
        if(mid < qr)
            res += query(k << 1 | 1, ql, qr), res %= mod;
        return res;
    }
};
Seg_tree T1;


signed main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> a[i];
    T1.build(1, 1, n);

    cin >> q;
    while(q --)
    {
        int opt;
        cin >> opt;
        int l, r;
        cin >> l >> r;
        if(opt == 1)
        {
            ll kk, d;
            cin >> kk >> d;
            T1.modify(1, l, r, kk % mod, d % mod);
        }   
        else
        {
            int m;
            cin >> m;
            cout << T1.query(1, l, r) % m << '\n';
        }
    }
}

2. 维护二次函数

例1. 智乃酱的平方数列

我们也可以用线段树来维护二次函数。

我们考虑对于 \([l,r]\) 添加平方数列,对于位置 \(\mathrm{x} \in [l, \mathrm{r}]\),增加的值应当是 \((x - (l - 1))^2\)。

展开后为: \(x^2+2(l-1)x+(l-1)^2\) 。那么这就是一个二次函数了,我们需要维护其系数。

我们需要三个懒标记,分别维护的是二次项 \(x^2\)的系数和,一次项 \(x\) 的系数和以及常数项的系数和。

那么若要维护一次函数也同理。

#include <bits/stdc++.h>

using namespace std;
const int N = 500005;
typedef long long ll;
const ll mod = 1000000007;
int n, m;
int a[N];

struct Seg_Tree {
    struct node {
        int l, r;
        ll s;
        ll base1, base2;
        ll lazy1, lazy2, lazy3;
    } seg[N * 4];
    void pushup(int k)
    {
        seg[k].s = (seg[k << 1].s + seg[k << 1 | 1].s) % mod;
    }
    void set_tag(int k, ll lazy1, ll lazy2, ll lazy3)
    {
        int len = seg[k].r - seg[k].l + 1;
        (seg[k].s += (seg[k].base1 * lazy1) % mod) %= mod;
        (seg[k].s += ((-2ll * seg[k].base2 * lazy2 % mod) + mod) % mod) %= mod;
        (seg[k].s += (1ll * len * lazy3 % mod)) %= mod;

        (seg[k].lazy1 += lazy1) %= mod;
        (seg[k].lazy2 += lazy2) %= mod;
        (seg[k].lazy3 += lazy3) %= mod;
    }
    void pushdown(int k)
    {
        if(seg[k].lazy1 || seg[k].lazy2 || seg[k].lazy3)
        {
            set_tag(k << 1, seg[k].lazy1, seg[k].lazy2, seg[k].lazy3);
            set_tag(k << 1 | 1, seg[k].lazy1, seg[k].lazy2, seg[k].lazy3);
            seg[k].lazy1 = seg[k].lazy2 = seg[k].lazy3 = 0;
        }
    }
    void build(int k, int l, int r)
    {
        seg[k].l = l, seg[k].r = r;
        if(l == r) {
            seg[k].s = a[l];
            seg[k].base1 = 1ll * l * l % mod;
            seg[k].base2 = l % mod;
            return;
        }
        int mid = (l + r) >> 1;
        build(k << 1, l, mid);
        build(k << 1 | 1, mid + 1, r);
        seg[k].base1 = (seg[k << 1].base1 + seg[k << 1 | 1].base1) % mod;
        seg[k].base2 = (seg[k << 1].base2 + seg[k << 1 | 1].base2) % mod;
        pushup(k);
    }
    void modify(int k,int ql, int qr, ll v)
    {
        int l = seg[k].l, r = seg[k].r;
        if(ql <= l && r <= qr)
        {
            set_tag(k, 1, v, v * v % mod);
            return;
        }
        pushdown(k);
        int mid = (l + r) >> 1;
        if(ql <= mid)
            modify(k << 1, ql, qr, v);
        if(mid < qr)
            modify(k << 1 | 1, ql, qr, v);
        pushup(k);
    }
    ll query(int k, int ql, int qr)
    {
        int l = seg[k].l, r = seg[k].r;
        if(ql <= l && r <= qr)
            return seg[k].s;
        pushdown(k);
        int mid = (l + r) >> 1;
        ll res = 0;
        if(ql <= mid)
            res += query(k << 1, ql, qr), res %= mod;
        if(mid < qr)
            res += query(k << 1 | 1, ql, qr), res %= mod;
        return res;
    }
};
Seg_Tree T1;

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n >> m;
    T1.build(1, 1, n);
    
    while(m --)
    {
        int opt, l, r;
        cin >> opt;
        cin >> l >> r;
        if(opt == 1)
            T1.modify(1, l, r, l - 1);
        else 
            cout << T1.query(1, l, r) << '\n';
    }
}

标签:opt,数学公式,int,线段,cin,维护,ll,等差数列,mod
From: https://www.cnblogs.com/DM11/p/17035995.html

相关文章

  • hdu:张煊的金箍棒(2)(线段树)
    ProblemDescription张煊的金箍棒升级了!升级后的金箍棒是由几根相同长度的金属棒连接而成(最开始都是铜棒,从1到N编号);张煊作为金箍棒的主人,可以对金箍棒施以任意的变换,每......
  • hdu:张煊的金箍棒(3)(线段树)
    ProblemDescription张煊的金箍棒升级了!升级后的金箍棒是由N段相同长度的金属棒连接而成(最开始每段金属棒的价值都是1,从1到N编号);张煊作为金箍棒的主人,可以对金箍棒任意......
  • P14_协同工作-开发者的权限说明以及如何维护项目成员
    不同项目成员对应的权限开发者的权限说明开发者权限:可使用小程序开发者工具及对小程序的功能进行代码开发体验者权限:可使用体验版小程序登录权限:可登录小程序管理后......
  • P14_协同工作-开发者的权限说明以及如何维护项目成员
    不同项目成员对应的权限开发者的权限说明开发者权限:可使用小程序开发者工具及对小程序的功能进行代码开发体验者权限:可使用体验版小程序登录权限:可登录小程序管理后......
  • P14_协同工作-开发者的权限说明以及如何维护项目成员
    不同项目成员对应的权限开发者的权限说明开发者权限:可使用小程序开发者工具及对小程序的功能进行代码开发体验者权限:可使用体验版小程序登录权限:可登录小程序管理后......
  • P14_协同工作-开发者的权限说明以及如何维护项目成员
    不同项目成员对应的权限开发者的权限说明开发者权限:可使用小程序开发者工具及对小程序的功能进行代码开发体验者权限:可使用体验版小程序登录权限:可登录小程序管理......
  • 【学习笔记 / 数据结构】线段树进阶
    扫描线【洛谷模板题传送门】思想以一条法线从下往上扫描整个图形,图形面积并即为\(\sum\limits_{i=1}^{n-1}len_i\times\left(h_{i+1}-h_i\right)\),其中\(len_i\)......
  • 【Unity TIL】6. 如何判断两条线段是否相交
    AABB碰撞检测,也就是轴对齐碰撞检测,用平行于x,y轴的矩形表示物体。如何判断两个矩形是否相撞,可以通过分别判断x,y轴上的线段是否相交。假设线段分别为(s1,e1),(s2,e2),判......
  • Blazor与Vue标签代码的可维护性对比
    通过一个简单示例来进行对比,Vue的ElementUI组件的行内编辑:Blazor的AntDesginBlazor组件的行内编辑:区别:el-table-column的label属性相当于Column的Title属性,这个是没......
  • 软件测试之维护性测试
    维护性测试用于评估系统能够被预期的维护人员修改的有效性和效率的程度,可从模块化、可重用性、易分析性、易修改性、易测试性、易维护性1)模块化:评估由独立组件组成......