给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。 输入格式 第一行输入一个数字 n。 第二行输入 n 个数字，第 i 个数字为 a i ​ ，以空格隔开。 接下来输入 n 行询问，每行输入四个数字 o p t opt、 l、 r、 c，以空格隔开。 若 o p t = 0 opt=0，表示将位于 [ , ] [l,r] 的之间的数字都加 c。 若 o p t = 1 opt=1，表示询问 a r ​ 的值（ l 和 c 忽略）。不要暴力C++

算法1

线段树

对于每个节点，维护该节点代表区间的总和sum和区间加值add，查询时将节点代表区间和查询到的add值相加后返回，更新时将add值赋给该节点，并将 add值“打标记”下放至子节点，这样在查询和更新子节点时就可以将父节点的add值加上去了。

时间复杂度

查询和更新都是O(logn)的，共n个数，因此总时间复杂度为O(nlogn)。

参考文献

最长上升子序列问题有nlogn的解法吗？

C++ 代码

算法2

线段树II

对于线段树节点不再维护区间和sum，而是将区间分治成若干部分，每部分维护该部分加的值sum，查询时将节点代表区间分治为若干部分后查询对应部分的sum值并加上区间加值add，更新时将add值标记至左右子节点并累加对应部分的sum值至该节点即可。

参考文献

线段树O(len^2logn)。

C++ 代码

相关问题

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。 输入格式 第一行输入一个数字 n。 第二行输入 n 个数字，第 i 个数字为 a i ​ ，以空格隔开。 接下来输入 n 行询问，每行输入四个数字 o p t opt、 l、 r、 c，以空格隔开。 若 o p t = 0 opt=0，表示将位于 [ , ] [l,r] 的之间的数字都加 c。 若 o p t = 1 opt=1，表示询问 a r ​ 的值（ l 和 c 忽略）。用C++做出来

题目描述

给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。

输入格式

第一行输入一个数字 n。

第二行输入 n 个数字，第 i 个数字为 ai ，以空格隔开。

接下来输入 n 行询问，每行输入四个数字 opt、l、r、c，以空格隔开。

若 opt=0，表示将位于[l,r]之间的数字都加c。

若 opt=1，表示询问 ai 的值（l和c忽略）。

输出格式

对于每个查询，输出一个整数表示结果，每个结果占一行。

样例输入

5
1 2 3 4 5
1 1 1 0
1 2 2 1
1 3 3 2
1 4 4 3
1 5 5 4

样例输出

1
3
5
7
9

算法1

(树状数组) $O(nlogn)$

树状数组做区间修改，单点查询

时间复杂度

树状数组做区间修改，单点查询，时间复杂度为 $O(nlogn)$

C++ 代码

算法2

(线段树) $O(nlogn)$

线段树做区间修改，单点查询

时间复杂度

线段树做区间修改，单点查询，时间复杂度为 $O(nlogn)$

C++ 代码

定义一个fibonacci数列函数，从键盘输入一个整数n，求第n项的fibonacci数列值

题目要求编写一个 Fibonacci 数列的函数，通过输入一个整数 n，在 Fibonacci 数列中找到第 n 项的值。

Fibonacci 数列是指：前两项是 0 和 1，从第三项开始，每一项都等于前两项的和。

因此，我们可以使用递归方式来找到第 n 项的值，具体步骤如下：

1. 如果 n 等于 0，返回 0；
2. 如果 n 等于 1，返回 1；
3. 如果 n 大于 1，返回第 n-1 项和第 n-2 项的和。

代码如下所示：

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

# 测试一下
print(fibonacci(0)) # 0
print(fibonacci(1)) # 1
print(fibonacci(2)) # 1
print(fibonacci(3)) # 2
print(fibonacci(4)) # 3
print(fibonacci(5)) # 5

输出结果为：

0
1
1
2
3
5