给出一个长为 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

编写一个定义一个Fibonacci数列函数，输入n，求第n项Fibonacci数列值

好的，以下是一个Python语言的Fibonacci数列函数，可以输入一个整数n，返回第n项的Fibonacci数列值：

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

你可以调用这个函数并输入一个正整数n来测试它的功能。