#树状数组#洛谷 3368 【模（mú）板】树状数组 2

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

线段树做法：详见

树状数组：

上面那个网址也说了，使用差分数组b[i]=a[i]-a[i-1]使b[1……i]=a[i],再用树状数组求出来。

---

代码

#include <cstdio>
#include <cctype>
#define ll long long
using namespace std;
ll n,a[500001],m;
ll lowbit(ll x){return x&(-x);}
ll in(){ll ans=0; char c=getchar(); int 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;
}
void add(ll x,ll k){while (x<=n){a[x]+=k;x+=lowbit(x);}
}
ll sum(ll x){ll ans=0;while (x>0){ans+=a[x];x-=lowbit(x);}return ans;
}
int main(){n=in(); m=in();for (ll i=1,o=0,x;i<=n;i++) x=in(),add(i,x-o),o=x;while (m--){ll q,l,r,x; q=in();if (q==1){l=in(); r=in(); x=in(); add(r+1,-x); add(l,x);}else {x=in(); printf("%lld\n",sum(x));}}return 0;
}

这篇关于#树状数组#洛谷 3368 【模（mú）板】树状数组 2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---