#树状数组，线段树#洛谷 3374 【模(mú)板】树状数组 1

本文主要是介绍#树状数组，线段树#洛谷 3374 【模(mú)板】树状数组 1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

树状数组单点修改和区间查询不想多讲

#include <cstdio>
#include <cctype>
using namespace std;
int a[500001],n,m;
int in(){char c=getchar(); int ans=0,f=1;while (!isdigit(c)&&c!='-') c=getchar();if (c=='-') f=-f,c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans*f;
}
int lowbit(int x){return x&(-x);}
void add(int l,int r){while (l<=n){a[l]+=r;l+=lowbit(l);}
}
int ask(int x){int ans=0;while (x>0){ans+=a[x];x-=lowbit(x);}return ans;
}
int main(){int l,r,q;n=in(); m=in();for (int i=1;i<=n;i++) q=in(),add(i,q);for (int i=1;i<=m;i++){q=in(); l=in(); r=in();if (q==1) add(l,r);else printf("%d\n",ask(r)-ask(l-1));}return 0;
}

线段树

这里写图片描述

首先是建树

int build(int l,int r,int k){if (l==r) return tree[k].w=a[r];else return tree[k].w=build(l,(l+r)>>1,2*k)+build(((l+r)>>1)+1,r,2*k+1);
}

修改

void update(int l,int r,int x,int y,int k){if (l==x&&r==x) {tree[k].w+=y; return;}int mid=(l+r)>>1;if (x<=mid) update(l,mid,x,y,2*k); else update(mid+1,r,x,y,2*k+1);tree[k].w=tree[2*k].w+tree[2*k+1].w;
}

查找

void find(int l,int r,int x,int y,int k){if (x==l&&y==r) {ans+=tree[k].w;return;}int mid=(l+r)>>1;if (y<=mid) find(l,mid,x,y,2*k);else if (x>mid) find(mid+1,r,x,y,2*k+1);else find(l,mid,x,mid,2*k),find(mid+1,r,mid+1,y,2*k+1);return;
}

代码

#include <cstdio>
#include <cctype>
using namespace std;
struct node{int w,laz;}tree[2000001]; int a[500001],n,m,ans;
int build(int l,int r,int k){if (l==r) return tree[k].w=a[r];else return tree[k].w=build(l,(l+r)>>1,2*k)+build(((l+r)>>1)+1,r,2*k+1);
}
inline int in(){int ans=0,f=1; char c=getchar();while (!isdigit(c)&&c!='-') c=getchar();if (c=='-') f=-f,c=getchar();while (isdigit(c)) ans=ans*10+c-48,c=getchar();return ans*f;
}
void update(int l,int r,int x,int y,int k){if (l==x&&r==x) {tree[k].w+=y; return;}int mid=(l+r)>>1;if (x<=mid) update(l,mid,x,y,2*k); else update(mid+1,r,x,y,2*k+1);tree[k].w=tree[2*k].w+tree[2*k+1].w;
}
void find(int l,int r,int x,int y,int k){if (x==l&&y==r) {ans+=tree[k].w;return;}int mid=(l+r)>>1;if (y<=mid) find(l,mid,x,y,2*k);else if (x>mid) find(mid+1,r,x,y,2*k+1);else find(l,mid,x,mid,2*k),find(mid+1,r,mid+1,y,2*k+1);return;
}
void in1(int &x,int &y){x=in();y=in();}
int main(){n=in(); m=in();for (int i=1;i<=n;i++) a[i]=in();build(1,n,1);	while (m--){int q=in(),x,y;ans=0;in1(x,y); if (q==1) update(1,n,x,y,1);else find(1,n,x,y,1),printf("%d\n",ans);}return 0;
}