#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define left(i) (2*i + 1)
#define right(i) (2*i + 2)
#define parent(i) ((i-1)/2)
#include <vector>
template<class T>
class SegmentTree
{
public:
SegmentTree(std::vector<T> data, T value, T (*combine)(T obj1, T obj2));
SegmentTree(T ar[], int n, T value, T (*combine)(T obj1, T obj2));
T query(int l, int r);
void update(int idx, T val);
//TODO lazy propagation
private:
T *tree;
void buildTree(std::vector<T> data);
int segTreeSize;
T valueForExtraNodes;
T (*combine)(T obj1, T obj2);
int calculateSize(int n);
T queryHelper(int l,int r, int st, int ed, int node);
};
template<class T> SegmentTree<T>::SegmentTree(std::vector<T> data,
T value, T (*combine)(T obj1, T obj2))
{
this->combine = combine;
valueForExtraNodes = value;
segTreeSize = calculateSize(data.size());
buildTree(data);
}
template<class T> SegmentTree<T>::SegmentTree(T ar[], int n,
T value, T (*combine)(T obj1, T obj2))
{
this->combine = combine;
valueForExtraNodes = value;
segTreeSize = calculateSize(n);
std::vector<T> data;
for(int i = 0; i < n; i++)
data.push_back(ar[i]);
buildTree(data);
}
template<class T> int SegmentTree<T>::calculateSize(int n)
{
int pow2 = 1;
while( pow2 < n)
{
pow2 = pow2 << 1;
}
return 2*pow2 - 1;
}
template<class T> T SegmentTree<T>::query(int l, int r)
{
int st = 0, ed = segTreeSize/2;
return queryHelper(l, r, st, ed, 0);
}
template<class T> T SegmentTree<T>::queryHelper(int l,int r, int st, int ed, int node)
{
if( (r < st) || (l > ed) || (l > r) )
return valueForExtraNodes;
if(st >= l && ed <= r)
return tree[node];
T leftVal = queryHelper(l, r, st, (st + ed)/2, left(node));
T rightVal = queryHelper(l, r, (st+ed)/2 + 1, ed, right(node));
return combine(leftVal, rightVal);
}
template<class T> void SegmentTree<T>::buildTree(std::vector<T> data)
{
int n = data.size();
tree = new T[segTreeSize];
int extraNodes = (segTreeSize/2 + 1) - n;
for(int i = segTreeSize - 1; i >= 0; i--)
{
if(extraNodes>0)
{
tree[i] = valueForExtraNodes;
extraNodes--;
}
else if(n>0)
{
tree[i] = data[n-1];
n--;
}
else
tree[i] = combine(tree[left(i)], tree[right(i)]);
}
}
template<class T> void SegmentTree<T>::update(int idx, T val)
{
int segTreeIdx = (segTreeSize/2) + idx;
tree[segTreeIdx] = val;
while(parent(segTreeIdx) >= 0)
{
segTreeIdx = parent(segTreeIdx);
if(right(segTreeIdx) < segTreeSize)
tree[segTreeIdx] = combine(tree[left(segTreeIdx)], tree[right(segTreeIdx)]);
if(segTreeIdx == 0)
break;
}
}
ll sum(ll x,ll y) { return x+y; }
int main()
{
int n,q;
cin>>n>>q;
vector<ll> v(n), zero(n,0);
for(int i=0;i<n;i++)
cin >> v[i];
SegmentTree<ll> rangeSumQueries(zero, 0, sum);
while(q--)
{
int t,l,r,u;
cin >> t;
if(t==1)
{
cin >> l >> r>> u;
ll actual_val_l = rangeSumQueries.query(l-1,l-1);
ll actual_val_r = rangeSumQueries.query(r,r);
rangeSumQueries.update(l-1,actual_val_l + u);
rangeSumQueries.update(r,actual_val_r - u);
}
else
{
cin >> u;
cout<<v[u-1] + rangeSumQueries.query(0,u-1)<<'\n';
}
}
return 0;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KI2RlZmluZSBsbCBsb25nIGxvbmcKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKI2RlZmluZSBsZWZ0KGkpICgyKmkgKyAxKQojZGVmaW5lIHJpZ2h0KGkpICgyKmkgKyAyKQojZGVmaW5lIHBhcmVudChpKSAoKGktMSkvMikKI2luY2x1ZGUgPHZlY3Rvcj4KCnRlbXBsYXRlPGNsYXNzIFQ+CmNsYXNzIFNlZ21lbnRUcmVlCnsKICAgIHB1YmxpYzoKICAgICAgICBTZWdtZW50VHJlZShzdGQ6OnZlY3RvcjxUPiBkYXRhLCBUIHZhbHVlLCBUICgqY29tYmluZSkoVCBvYmoxLCBUIG9iajIpKTsKICAgICAgICBTZWdtZW50VHJlZShUIGFyW10sIGludCBuLCBUIHZhbHVlLCBUICgqY29tYmluZSkoVCBvYmoxLCBUIG9iajIpKTsKICAgICAgICBUIHF1ZXJ5KGludCBsLCBpbnQgcik7CiAgICAgICAgdm9pZCB1cGRhdGUoaW50IGlkeCwgVCB2YWwpOwogICAgICAgIC8vVE9ETyBsYXp5IHByb3BhZ2F0aW9uCiAgICBwcml2YXRlOgogICAgICAgIFQgKnRyZWU7CiAgICAgICAgdm9pZCBidWlsZFRyZWUoc3RkOjp2ZWN0b3I8VD4gZGF0YSk7CiAgICAgICAgaW50IHNlZ1RyZWVTaXplOwogICAgICAgIFQgdmFsdWVGb3JFeHRyYU5vZGVzOwogICAgICAgIFQgKCpjb21iaW5lKShUIG9iajEsIFQgb2JqMik7CiAgICAgICAgaW50IGNhbGN1bGF0ZVNpemUoaW50IG4pOwogICAgICAgIFQgcXVlcnlIZWxwZXIoaW50IGwsaW50IHIsIGludCBzdCwgaW50IGVkLCBpbnQgbm9kZSk7Cn07Cgp0ZW1wbGF0ZTxjbGFzcyBUPiBTZWdtZW50VHJlZTxUPjo6U2VnbWVudFRyZWUoc3RkOjp2ZWN0b3I8VD4gZGF0YSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgVCB2YWx1ZSwgVCAoKmNvbWJpbmUpKFQgb2JqMSwgVCBvYmoyKSkKewogICB0aGlzLT5jb21iaW5lID0gY29tYmluZTsKICAgdmFsdWVGb3JFeHRyYU5vZGVzID0gdmFsdWU7CiAgIHNlZ1RyZWVTaXplID0gY2FsY3VsYXRlU2l6ZShkYXRhLnNpemUoKSk7CiAgIGJ1aWxkVHJlZShkYXRhKTsKfQoKdGVtcGxhdGU8Y2xhc3MgVD4gU2VnbWVudFRyZWU8VD46OlNlZ21lbnRUcmVlKFQgYXJbXSwgaW50IG4sCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgVCB2YWx1ZSwgVCAoKmNvbWJpbmUpKFQgb2JqMSwgVCBvYmoyKSkKewogICB0aGlzLT5jb21iaW5lID0gY29tYmluZTsKICAgdmFsdWVGb3JFeHRyYU5vZGVzID0gdmFsdWU7CiAgIHNlZ1RyZWVTaXplID0gY2FsY3VsYXRlU2l6ZShuKTsKCiAgIHN0ZDo6dmVjdG9yPFQ+IGRhdGE7CiAgIGZvcihpbnQgaSA9IDA7IGkgPCBuOyBpKyspCiAgICAgICAgIGRhdGEucHVzaF9iYWNrKGFyW2ldKTsKCiAgIGJ1aWxkVHJlZShkYXRhKTsKfQoKCnRlbXBsYXRlPGNsYXNzIFQ+IGludCBTZWdtZW50VHJlZTxUPjo6Y2FsY3VsYXRlU2l6ZShpbnQgbikKewogICAgaW50IHBvdzIgPSAxOwogICAgd2hpbGUoIHBvdzIgPCBuKQogICAgewogICAgICAgIHBvdzIgPSBwb3cyIDw8IDE7CiAgICB9CiAgICByZXR1cm4gMipwb3cyIC0gMTsKfQoKdGVtcGxhdGU8Y2xhc3MgVD4gVCBTZWdtZW50VHJlZTxUPjo6cXVlcnkoaW50IGwsIGludCByKQp7CiAgICBpbnQgc3QgPSAwLCBlZCA9IHNlZ1RyZWVTaXplLzI7CiAgICByZXR1cm4gcXVlcnlIZWxwZXIobCwgciwgc3QsIGVkLCAwKTsKfQoKdGVtcGxhdGU8Y2xhc3MgVD4gVCBTZWdtZW50VHJlZTxUPjo6cXVlcnlIZWxwZXIoaW50IGwsaW50IHIsIGludCBzdCwgaW50IGVkLCBpbnQgbm9kZSkKewogICAgaWYoIChyIDwgc3QpIHx8IChsID4gZWQpIHx8IChsID4gcikgKQogICAgICAgIHJldHVybiB2YWx1ZUZvckV4dHJhTm9kZXM7CiAgICBpZihzdCA+PSBsICYmIGVkIDw9IHIpCiAgICAgICAgcmV0dXJuIHRyZWVbbm9kZV07CiAgICBUIGxlZnRWYWwgPSBxdWVyeUhlbHBlcihsLCByLCBzdCwgKHN0ICsgZWQpLzIsIGxlZnQobm9kZSkpOwogICAgVCByaWdodFZhbCA9IHF1ZXJ5SGVscGVyKGwsIHIsIChzdCtlZCkvMiArIDEsIGVkLCByaWdodChub2RlKSk7CiAgICByZXR1cm4gY29tYmluZShsZWZ0VmFsLCByaWdodFZhbCk7Cn0KCnRlbXBsYXRlPGNsYXNzIFQ+IHZvaWQgU2VnbWVudFRyZWU8VD46OmJ1aWxkVHJlZShzdGQ6OnZlY3RvcjxUPiBkYXRhKQp7CiAgIGludCBuID0gZGF0YS5zaXplKCk7CiAgIHRyZWUgPSBuZXcgVFtzZWdUcmVlU2l6ZV07CiAgIGludCBleHRyYU5vZGVzID0gKHNlZ1RyZWVTaXplLzIgKyAxKSAtIG47CiAgIGZvcihpbnQgaSA9IHNlZ1RyZWVTaXplIC0gMTsgaSA+PSAwOyBpLS0pCiAgIHsKICAgICAgIGlmKGV4dHJhTm9kZXM+MCkKICAgICAgICAgICB7CiAgICAgICAgICAgICAgIHRyZWVbaV0gPSB2YWx1ZUZvckV4dHJhTm9kZXM7CiAgICAgICAgICAgICAgIGV4dHJhTm9kZXMtLTsKICAgICAgICAgICB9CiAgICAgICBlbHNlIGlmKG4+MCkKICAgICAgICAgICB7CiAgICAgICAgICAgICAgIHRyZWVbaV0gPSBkYXRhW24tMV07CiAgICAgICAgICAgICAgIG4tLTsKICAgICAgICAgICB9CiAgICAgICBlbHNlCiAgICAgICAgICAgdHJlZVtpXSA9IGNvbWJpbmUodHJlZVtsZWZ0KGkpXSwgdHJlZVtyaWdodChpKV0pOwogICB9Cn0KCnRlbXBsYXRlPGNsYXNzIFQ+IHZvaWQgU2VnbWVudFRyZWU8VD46OnVwZGF0ZShpbnQgaWR4LCBUIHZhbCkKewogICAgaW50IHNlZ1RyZWVJZHggPSAoc2VnVHJlZVNpemUvMikgKyBpZHg7CiAgICB0cmVlW3NlZ1RyZWVJZHhdID0gdmFsOwogICAgd2hpbGUocGFyZW50KHNlZ1RyZWVJZHgpID49IDApCiAgICB7CiAgICAgICAgc2VnVHJlZUlkeCA9IHBhcmVudChzZWdUcmVlSWR4KTsKICAgICAgICBpZihyaWdodChzZWdUcmVlSWR4KSA8IHNlZ1RyZWVTaXplKQogICAgICAgICAgdHJlZVtzZWdUcmVlSWR4XSA9IGNvbWJpbmUodHJlZVtsZWZ0KHNlZ1RyZWVJZHgpXSwgdHJlZVtyaWdodChzZWdUcmVlSWR4KV0pOwogICAgICAgIGlmKHNlZ1RyZWVJZHggPT0gMCkKICAgICAgICAgICAgYnJlYWs7CiAgICB9Cn0KCmxsIHN1bShsbCB4LGxsIHkpIHsgcmV0dXJuIHgreTsgfQppbnQgbWFpbigpCnsKICAgIGludCBuLHE7CiAgICBjaW4+Pm4+PnE7CiAgICB2ZWN0b3I8bGw+IHYobiksIHplcm8obiwwKTsKICAgIGZvcihpbnQgaT0wO2k8bjtpKyspCiAgICAgICAgY2luID4+IHZbaV07CiAgICBTZWdtZW50VHJlZTxsbD4gcmFuZ2VTdW1RdWVyaWVzKHplcm8sIDAsIHN1bSk7CiAgICB3aGlsZShxLS0pCiAgICB7CiAgICAgICAgaW50IHQsbCxyLHU7CiAgICAgICAgY2luID4+IHQ7CiAgICAgICAgaWYodD09MSkKICAgICAgICB7CiAgICAgICAgICAgIGNpbiA+PiBsID4+IHI+PiB1OwogICAgICAgICAgICBsbCBhY3R1YWxfdmFsX2wgPSByYW5nZVN1bVF1ZXJpZXMucXVlcnkobC0xLGwtMSk7CiAgICAgICAgICAgIGxsIGFjdHVhbF92YWxfciA9IHJhbmdlU3VtUXVlcmllcy5xdWVyeShyLHIpOwogICAgICAgICAgICByYW5nZVN1bVF1ZXJpZXMudXBkYXRlKGwtMSxhY3R1YWxfdmFsX2wgKyB1KTsKICAgICAgICAgICAgcmFuZ2VTdW1RdWVyaWVzLnVwZGF0ZShyLGFjdHVhbF92YWxfciAtIHUpOwogICAgICAgIH0KICAgICAgICBlbHNlCiAgICAgICAgewogICAgICAgICAgICBjaW4gPj4gdTsKICAgICAgICAgICAgY291dDw8dlt1LTFdICsgcmFuZ2VTdW1RdWVyaWVzLnF1ZXJ5KDAsdS0xKTw8J1xuJzsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gMDsKfQoK