#Pbit11. 【例题1】单点修改区间查询

    ID: 178 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 普及+/提高- 上传者: 标签>树状数组赛制:OI来源:wyfoj http://127.0.0.1

【例题1】单点修改区间查询

【例题1】单点修改区间查询

题目描述

这是一道模板题。这是一道模板题。

给定数列a[1],a[2],...a[n],你需要依次进行q个操作,操作有两类:给定数列a[1],a[2],...a[n],你需要依次进行q个操作,操作有两类:

1 i x:给定i,x,将a[i]加上x;给定i,x,将a[i]加上x;

2 l r:$给定l,r,求\sum_{i=l}^r a[i]的值(换言之,求的a[l]+a[l+1]+....a[r]值)$。

输入格式

第一行包含2个正整数n,q,表示数列长度和询问个数。保证1<=n,q<=106第一行包含2个正整数n,q,表示数列长度和询问个数。保证1<=n,q<=10^6。 第二行n个整数,表示初始数列a[1],a[2],...a[n]。保证∣a[i]]<=106第二行n个整数,表示初始数列a[1],a[2],...a[n]。保证|a[i]]<=10^6。 接下来q行,每行一个操作,为以下两种之一:接下来q行,每行一个操作,为以下两种之一:

1 i x:给定i,x,将a[i]加上x;给定i,x,将a[i]加上x;

2 l r:给定l,r,求∑i=lra[i]的值。给定l,r,求\sum_{i=l}^r a[i]的值。

保证1<=l<=r<=n,∣x∣<=1061<=l<=r<=n,|x|<=10^6。

输出格式

对于每个2 l r操作输出一行,每行有一个整数,表示所求的结果。

数据范围

(原站未提供,导入后需人工补齐)

样例

3 2
1 2 3
1 2 0
2 1 3
6

提示

对于所有数据1<=n,q<=106,∣a[i]∣<=106,1<=l<=r<=n,∣x∣<=1061<=n,q<=10^6,|a[i]|<=10^6,1<=l<=r<=n,|x|<=10^6。