Problem A

發布時間: 2017年6月28日 09:29?? 最后更新: 2017年6月28日 13:03?? 時間限制: 1000ms?? 內存限制: 32M

描述

給定一個長度為n的序列a1,?a2, ...,?an

給出q個操作, 操作分為兩種

對于形如1?x?y?z的操作, 將下標介于[x,y]的元素加上z, 滿足1≤x≤y≤n,?1≤z≤105

對于形如2?x的操作, 輸出ax, 滿足1≤x≤n

9×104≤n≤105,?9×104≤q≤105,?1≤ai≤105

輸入

第一行兩個整數n,?q, 意義如上所述。
第二行n個整數, 表示序列a。
接下來q行, 每行第一個數為opt, 如果opt=1, 則后面緊跟三個數, 意義如上所述; 如果opt=2, 則后面緊跟一個數, 意義如上所述。

輸出

對于所有操作2, 輸出答案, 一行一個。

樣例輸入1 8 3 3 1 4 1 5 9 2 6 2 3 1 2 3 6 2 3 樣例輸出1 4 10

題解：

由于樹狀數組的求和功能是可以在LOG(N)的時間復雜度內完成，現在我們考慮把求某一個點的值劃歸到求某一段區間和的問題，這樣我們就可以構造序列

b[i] = a[i] - a[i-1],b[1] = a[i]

這樣的話，如果我要把某段區間[l,r]的值增加val,那么我只需要把b[l]增加val，然后b[r+1]減去val,就可以了

代碼：

#include <iostream> #include <cstdio> using namespace std; #define int long long const int MAX = 1e5+7; int a[MAX]; int b[MAX]; int n,q; int lowbit(int x){return x&(-x); } int sum(int pos){int ans = 0;while(pos){ans += b[pos];pos -= lowbit(pos);}return ans; } void add(int pos,int val){while(pos <= n){b[pos] += val;pos += lowbit(pos);} } main(){scanf("%lld%lld",&n,&q);for(int i = 1;i <= n;i++){scanf("%lld",&a[i]);add(i,a[i]-a[i-1]);}while(q--){int op;scanf("%lld",&op);if(op == 1){int a,b,c;scanf("%lld%lld%lld",&a,&b,&c);add(a,c);add(b + 1,-c);}else{int a;scanf("%lld",&a);printf("%lld\n",sum(a));}}return 0; }

總結

以上是生活随笔為你收集整理的2017西安交大ACM小学期数据结构 [分块，区间修改，单点查询]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。