深圳住房建设局网站申报,河南住房和城乡建设部网站,淘宝网站上的图片是怎么做的,神马seo服务【模板】树状数组 2
题目描述
如题#xff0c;已知一个数列#xff0c;你需要进行下面两种操作#xff1a; 将某区间每一个数加上 x x x#xff1b; 求出某一个数的值。
输入格式
第一行包含两个整数 N N N、 M M M#xff0c;分别表示该数列数字的个数和操作的总…【模板】树状数组 2
题目描述
如题已知一个数列你需要进行下面两种操作 将某区间每一个数加上 x x x 求出某一个数的值。
输入格式
第一行包含两个整数 N N N、 M M M分别表示该数列数字的个数和操作的总个数。
第二行包含 N N N 个用空格分隔的整数其中第 i i i 个数字表示数列第 $i $ 项的初始值。
接下来 M M M 行每行包含 2 2 2 或 4 4 4个整数表示一个操作具体如下
操作 1 1 1 格式1 x y k 含义将区间 [ x , y ] [x,y] [x,y] 内每个数加上 k k k
操作 2 2 2 格式2 x 含义输出第 x x x 个数的值。
输出格式
输出包含若干行整数即为所有操作 2 2 2 的结果。
样例 #1
样例输入 #1
5 5
1 5 4 2 3
1 2 4 2
2 3
1 1 5 -1
1 3 5 7
2 4样例输出 #1
6
10提示
样例 1 解释 故输出结果为 6、10。 数据规模与约定
对于 30 % 30\% 30% 的数据 N ≤ 8 N\le8 N≤8 M ≤ 10 M\le10 M≤10
对于 70 % 70\% 70% 的数据 N ≤ 10000 N\le 10000 N≤10000 M ≤ 10000 M\le10000 M≤10000
对于 100 % 100\% 100% 的数据 1 ≤ N , M ≤ 500000 1 \leq N, M\le 500000 1≤N,M≤500000 1 ≤ x , y ≤ n 1 \leq x, y \leq n 1≤x,y≤n保证任意时刻序列中任意元素的绝对值都不大于 2 30 2^{30} 230。 #includemap
#includeset
#includestack
#includecmath
#includequeue
#includestring
#includebitset
#includecstring
#includeiostream
#includealgorithm
#includenumeric
#includeiomanip
#define endl \n
//#define x first
//#define y second
using namespace std;typedef long long ll;
typedef pairint, intPII;
const int N3e510;
const int MOD1e9 7;
const int INF0X3F3F3F3F;
const int dx[]{-1,1,0,0,-1,-1,1,1};
const int dy[]{0,0,-1,1,-1,1,-1,1};
const int M 1e6 10;int tree[M];//此时树状数组维护的是差分数组
int n, m;int bit(int x)
{return x -x;
}
void add(int i, int x)
{while(i n){tree[i] x;i bit(i);}
}int sum(int i)
{int res 0;while(i 0){res tree[i];i - bit(i);}return res;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin n m;for(int i 1; i n; i ){int x;cin x;add(i, x);add(i 1, -x);}while(m --){int a, x, y, k;cin a;if(a 1) {cin x y k;add(x, k);add(y 1, -k);}if(a 2){cin x;cout sum(x);cout endl;}}return 0;
}
