斐波纳契数列 线段树的维护

2024-05-07 08:38
文章标签 维护 数列 线段 波纳契

本文主要是介绍斐波纳契数列 线段树的维护,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

像一般的数列维护一样,这题也差不多。有一个数列a,修改操作是将a[i] .. a[j]的值都加上一个d,询问操作就有点不同,给出i和j,求出a[i] * fib(0) + a[i + 1] * fib(1) + a[i + 2] * fib(2) + ... + a[j] * fib(j - i)模上一个数的结果。其中fib就是斐波纳契数列,即fib(0) = fib(1) = 1,对于fib(i)(> 1), fib(i) = fib(i -1) + fib(i - 2)。

如果这个线段树要支持某个操作,那必须要实现合并的操作,也就是在线段树的某个结点,它如何将两个儿子的信息合并成一个。对于这题,就需要实现一个:

已知a[i] * fib(0) + a[i + 1] * fib(1) + a[i + 2] * fib(2) + ... + a[j] * fib(j - i)或者保存多一些需要的信息,怎样求出a[i] * fib(0 + k) + a[i + 1] * fib(1 + k) + a[i + 2] * fib(2 + k) + ... + a[j] * fib(j - i + k)。

斐波纳契数列有一个奇特的性质,尝试如下的运算,得出的序列还是斐波纳契数列。

a  1  1  2  3  5  8  13  ....

b  1  2  3  5  8  13  21 ....

将同一个位置的相加(c[i] = a[i] + b[i]),得:

c  2  3  5  8  13  21  34 ....

再加加d[i] = b[i] + c[i],得:

d 3  5  8  13  21  34  55

如此看来,我们可以设:

X =  a[i] * fib(0) + a[i + 1] * fib(1) + a[i + 2] * fib(2) + ... + a[j] * fib(j - i);

Y =  a[i] * fib(1) + a[i + 1] * fib(2) + a[i + 2] * fib(3) + ... + a[j] * fib(j - i + 1);

那么:

X + Y  = a[i] * fib(2) + a[i + 1] * fib(3) + a[i + 2] * fib(4) + ... + a[j] * fib(j - i + 2);

X + 2Y = a[i] * fib(3) + a[i + 1] * fib(4) + a[i + 2] * fib(5) + ... + a[j] * fib(j - i + 3);

2X + 3Y = a[i] * fib(4) + a[i + 1] * fib(5) + a[i + 2] * fib(6) + ... + a[j] * fib(j - i + 4);

3X + 5Y = a[i] * fib(5) + a[i + 1] * fib(6) + a[i + 2] * fib(7) + ... + a[j] * fib(j - i + 5);

....

fib(k - 2) * X + fib(k - 1) * Y = a[i] * fib(0 + k) + a[i + 1] * fib(1 + k) + a[i + 2] * fib(2 + k) + ... + a[j] * fib(j - i + k)   (k > 1),k = 0,k = 1的情况额外处理,fib数列预处理。

这样,我们就可以实现维护了,需要保存两个信息,就是上述的X,Y。接着就是信息传递的操作,也就是整段都加上d。

也就是已知a[i] * fib(0) + a[i + 1] * fib(1) + a[i + 2] * fib(2) + ... + a[j] * fib(j - i),求(a[i] + d) * fib(0) + (a[i + 1] + d) * fib(1) + (a[i + 2] + d) * fib(2) + ... + (a[j]  + d) * fib(j - i)。

通过拆分得:a[i] * fib(0) + a[i + 1] * fib(1) + a[i + 2] * fib(2) + ... + a[j] * fib(j - i) + d * fib(0) + d * fib(1) + d * fib(2) + ... + d * fib(j - i)

a[i] * fib(0) + a[i + 1] * fib(1) + a[i + 2] * fib(2) + ... + a[j] * fib(j - i) + d * (fib(0) + fib(1) + fib(2) + ... + fib(j - i))

fib的数列和有个定理:fib(0) + fib(1) + fib(2) + ... + fib(i) = fib(i + 2) - 1。这样又可以实现信息传递的操作了。问题到此就解决了。此外,我们可以从fib的矩阵乘法中联想到合并信息的方法,本质是一样的。

对于一些比较难维护的数据,可以通过列公式等方法找出其中的规律,哪怕没有什么规律,我们也能从中得到一些启发。还可以想想另一些方法,即使它们看起来是不能解决问题的。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;const ll mod = 1000000000LL;
const int N = 200007;
int n, m;
ll fib[N], X[N], Y[N];int nnode = 1;
struct Node
{Node *lch, *rch;int lo, hi;ll flag;pii dat;inline int mi(){return (lo + hi) >> 1;}inline int size(){return hi - lo;}
}node[N << 1], *root = &node[0];inline pii Calc(pii a, int k)
{pii res;res.first = (a.first * (k == 1 ? 0LL : fib[k - 2]) % mod + a.second * fib[k - 1] % mod) % mod;res.second = (a.first * fib[k - 1] % mod +a.second * fib[k] % mod) % mod;return res;
}pii operator + (pii const &a, pii const &b) 
{return make_pair((a.first + b.first) % mod, (a.second + b.second) % mod);
}void Build(Node *p, int le, int ri)
{p -> lo = le;p -> hi = ri;p -> flag = 0LL;if (le + 1 == ri){scanf("%I64d\n", &p -> dat.first);p -> dat.second = p -> dat.first;p -> lch = p -> rch = NULL;}else {int mi = p -> mi();p -> lch = &node[nnode ++];p -> rch = &node[nnode ++];Build(p -> lch, le, mi);Build(p -> rch, mi, ri);p -> dat = p -> lch -> dat + Calc(p -> rch -> dat, mi - le);}
}void Update(Node *p, ll flag)
{p -> flag += flag;p -> dat.first = (flag * (fib[p -> size() + 1] - 1LL) + p -> dat.first) % mod;p -> dat.second = (flag * (fib[p -> size() + 2] - 2LL) +p -> dat.second) % mod;
}void Modify(Node *p, int le, int ri, ll delta)
{if (le <= p -> lo && ri >= p -> hi)Update(p, delta);else {if (p -> flag) {Update(p -> lch, p -> flag);Update(p -> rch, p -> flag);p -> flag = 0LL;}int mi = p -> mi();if (le < mi) Modify(p -> lch, le, ri, delta);if (ri > mi) Modify(p -> rch, le, ri, delta);p -> dat = p -> lch -> dat + Calc(p -> rch -> dat, p -> lch -> size());}
}pii Ask(Node *p, int le, int ri)
{if (le <= p -> lo && ri >= p -> hi)return p -> dat;if (p -> flag) {Update(p -> lch, p -> flag);Update(p -> rch, p -> flag);p -> flag = 0LL;}int mi = p -> mi();if (le < mi && ri > mi)return Ask(p -> lch, le, ri) + Calc(Ask(p -> rch, le, ri), p -> lch -> hi - max(le, p -> lch -> lo));else if (le < mi) return Ask(p -> lch, le, ri);else return Ask(p -> rch, le, ri);
}void Init()
{scanf("%d%d\n", &n, &m);fib[0] = fib[1] = 1;for (int i = 2; i < n; i ++)fib[i] = (fib[i - 1] + fib[i - 2]) % mod;Build(root, 0, n);
}void Solve()
{while (m --){int tmp, le, ri;scanf("%d%d%d", &tmp, &le, &ri);if (tmp == 2){scanf("\n");printf("%I64d\n", Ask(root, le - 1, ri).first);}else {ll di;scanf("%I64d\n", &di);Modify(root, le - 1, ri, di);}}
}int main()
{freopen("fib.in", "r", stdin);freopen("fib.out", "w", stdout);Init();Solve();return 0;
}


这篇关于斐波纳契数列 线段树的维护的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/966865

相关文章

poj3468(线段树成段更新模板题)

题意:包括两个操作:1、将[a.b]上的数字加上v;2、查询区间[a,b]上的和 下面的介绍是下解题思路: 首先介绍  lazy-tag思想:用一个变量记录每一个线段树节点的变化值,当这部分线段的一致性被破坏我们就将这个变化值传递给子区间,大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作,那么就从根节点[1,n]开始调用update函数进行操作,如果刚好执行到一个子节点,

hdu1394(线段树点更新的应用)

题意:求一个序列经过一定的操作得到的序列的最小逆序数 这题会用到逆序数的一个性质,在0到n-1这些数字组成的乱序排列,将第一个数字A移到最后一位,得到的逆序数为res-a+(n-a-1) 知道上面的知识点后,可以用暴力来解 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#in

hdu1689(线段树成段更新)

两种操作:1、set区间[a,b]上数字为v;2、查询[ 1 , n ]上的sum 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdl

hdu 1754 I Hate It(线段树,单点更新,区间最值)

题意是求一个线段中的最大数。 线段树的模板题,试用了一下交大的模板。效率有点略低。 代码: #include <stdio.h>#include <string.h>#define TREE_SIZE (1 << (20))//const int TREE_SIZE = 200000 + 10;int max(int a, int b){return a > b ? a :

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

poj 1127 线段相交的判定

题意: 有n根木棍,每根的端点坐标分别是 px, py, qx, qy。 判断每对木棍是否相连,当他们之间有公共点时,就认为他们相连。 并且通过相连的木棍相连的木棍也是相连的。 解析: 线段相交的判定。 首先,模板中的线段相交是不判端点的,所以要加一个端点在直线上的判定; 然后,端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的,所以要加是否端点相等的判断。 最后

HDU4737线段树

题目大意:给定一系列数,F(i,j)表示对从ai到aj连续求或运算,(i<=j)求F(i,j)<=m的总数。 const int Max_N = 100008 ;int sum[Max_N<<2] , x[Max_N] ;int n , m ;void push_up(int t){sum[t] = sum[t<<1] | sum[t<<1|1] ;}void upd

zoj 1721 判断2条线段(完全)相交

给出起点,终点,与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离,然后最短路。 2点可达条件:没有线段与这2点所构成的线段(完全)相交。 const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;

圆与线段的交点

poj 3819  给出一条线段的两个端点,再给出n个圆,求出这条线段被所有圆覆盖的部分占了整条线段的百分比。 圆与线段的交点 : 向量AB 的参数方程  P = A + t * (B - A)      0<=t<=1 ; 将点带入圆的方程即可。  注意: 有交点 0 <= t <= 1 ; 此题求覆盖的部分。 则 若求得 t  满足 ; double ask(d

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja