啥板子~~（言简意赅的我没有）~~
by 南城忆潇湘 @ 2018-10-15 20:16:32
@[御坂19000号](/space/show?uid=109181) ~~（言简意赅的我没有）~~
```
#include <cstdio>
struct node{ int l,r,lc,rc,c; } a[1000001];
int q[1000001],len=0,n=0,m=0;
void bt(int l,int r)
{
len++;
a[len].l=l;
a[len].r=r;
a[len].lc=-1;
a[len].rc=-1;
a[len].c=0;
int now=len;
if(l<r)
{
int mid=(l+r)/2;
a[len].lc=len+1,bt(l,mid);
a[now].rc=len+1,bt(mid+1,r);
}
}
void change(int now,int x,int t)
{
if(a[now].l==a[now].r)
{
a[now].c+=t;
return ;
}
int mid=(a[now].l+a[now].r)/2;
if(x<=mid)
{
change(a[now].lc,x,t);
}
else
{
change(a[now].rc,x,t);
}
a[now].c=a[a[now].lc].c+a[a[now].rc].c;
}
int findsum(int now,int l,int r)
{
if(a[now].l==l && a[now].r==r)
{
return a[now].c;
}
int mid=(a[now].l+a[now].r)/2;
if(r<=mid)
{
return findsum(a[now].lc,l,r);
}
else if(mid+1<=l)
{
return findsum(a[now].rc,l,r);
}
else
{
return findsum(a[now].lc,l,mid)+findsum(a[now].rc,mid+1,r);
}
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&q[i]);
}
bt(1,n);
for(int i=1;i<=n;i++)
{
change(1,i,q[i]);
}
for(int i=1;i<=m;i++)
{
int t=0,x=0,y=0;
scanf("%d %d %d",&t,&x,&y);
if(t==1)
{
change(1,x,y);
}
else if(t==2)
{
printf("%d\n",findsum(1,x,y));
}
}
return 0;
}
```
by Drinkkk @ 2018-10-15 20:17:21
可以去洛谷月赛找mcfx大佬的线段树（话说这题是mcfx出的题应该是他的线段树吧）（逃）
by 紫妹只有17岁 @ 2018-10-15 20:17:56
```cpp
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
class Segment_Tree{
private:
#define MAXN 100010
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid(x,y) ((x+y)>>1)
#define clear(x) memset(x,0,sizeof(x))
struct Node{
int l,r,tag,key;
}t[MAXN*4+4];
int n,val[MAXN+1],size,root;
inline void update(int now){
t[now].key=t[ls(now)].key+t[rs(now)].key;
}
inline void up(int now,int l,int r,const int key){
int L=max(l,t[now].l),R=min(r,t[now].r);
if(L>R) return; t[now].key+=(R-L+1)*key;
}
inline void pushdown(int now){
t[now].key+=(t[now].r-t[now].l+1)*t[now].tag;
t[ls(now)].tag+=t[now].tag;t[rs(now)].tag+=t[now].tag; t[now].tag=0;
}
void build(int now,int l,int r){
t[now].l=l,t[now].r=r; size++;
if(t[now].l==t[now].r){
t[now].key=val[l]; return ;
}
build(ls(now),l,mid(l,r));build(rs(now),mid(l,r)+1,r);
t[now].key=t[ls(now)].key+t[rs(now)].key;
}
public:
inline int get_n(){ return n; }
inline int get_size(){ return size; }
inline int get_root(){ return root=1; }
void pre(int N,int *A){
n=N; for(int i=1;i<=n;i++) val[i]=A[i]; build(1,1,N);
}
int ask(int now,int l,int r){
pushdown(now);
if(r<t[now].l||l>t[now].r) return 0;
if(t[now].l>=l&&t[now].r<=r) return t[now].key;
int cnt=0,mid=mid(t[now].l,t[now].r);
cnt=ask(ls(now),l,r)+ask(rs(now),l,r);update(now);
return cnt;
}
void add(int now,int l,int r,const int key){
pushdown(now);
if(r<t[now].l||l>t[now].r) return ;
if(t[now].l>=l&&t[now].r<=r){
t[now].tag=key; return ;
}
add(ls(now),l,r,key); add(rs(now),l,r,key);up(now,l,r,key);
}
}Tree;
int a[100001];
int main(){
}
```
by 南城忆潇湘 @ 2018-10-15 20:19:17
@[御坂19000号](/space/show?uid=109181) zkw线段树~嘻嘻~
```cpp
#include<cstdio>
long long d[2000010],n,m,t,k,s;
int x=1;
void build(){
for(int i=1;i<=n;i++)scanf("%lld",&d[i+x]);
for(int i=x-1;i>=1;i--)d[i]=d[i<<1]+d[i<<1|1];
}
void add(int k,int t){
d[x+k]+=t;int u=x+k;
while(u)u>>=1,d[u]=d[u<<1]+d[u<<1|1];
}
int query(int l,int r){
long long ans=0,s=l+x-1,t=r+x+1;
for (;s^t^1;s>>=1,t>>=1){
if(~s&1)ans+=d[s^1];
if( t&1)ans+=d[t^1];
}return ans;
}
int main(){
scanf("%lld%lld",&n,&m);
for(;x<n;x<<=1);
build();
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&t,&k,&s);
if(t==1)add(k,s);else printf("%lld\n",query(k,s));
}
}
```
by w23c3c3 @ 2018-10-15 20:25:03
为什么要发在【树状数组模板】里啊QAQ
by 哔哩哔哩 @ 2018-10-15 20:25:32
@[哔哩哔哩](/space/show?uid=41868) 我不知道……反正我用线段树做的……
by w23c3c3 @ 2018-10-15 20:28:30
谢谢大佬
by 御坂19000号 @ 2018-10-16 06:26:05
来自刚学线段树却过不了模板的蒟蒻
by 御坂19000号 @ 2018-10-16 06:26:37
指针的要吗
by Starduster @ 2018-10-28 16:57:55