題目

• 基本介紹
• 模板題目
• 代碼實現

基本介紹

這篇是樹狀數組模板2 主要內容有：
1.將某區間每一個數數加上x
2.求出某一個數的和
也就是說支持區間修改

我們可以看一下 Qi.DC 的想法 他說：“
我們在樹狀數組中可以用前 i 項的和來表示第 i 個數 那么當對 x ~ y 的區間進行修改的時候需要在樹狀數組中的第 x 個位置 + k 第 y + 1 個位置 -k 這樣便維護了這個樹狀數組 輸出時候直接輸出查詢即可”
這也就完成了區間修改

模板題目

見基本介紹

代碼實現

Qi.DC的思路

#include<iostream> #include<cstdio> #include<cctype>using namespace std;#define in = read()typedef long long ll;const ll size = 500000 + 1000;#define lowbit(x) (x & -x)ll n,m;ll tree[size];ll last,next;inline ll read(){ll num = 0 , f = 1; char ch = getchar();while(!isdigit(ch)){if(ch == '-') f = -1;ch = getchar();}while(isdigit(ch)){num = num*10 + ch - '0';ch = getchar();}return num*f; }inline void add(ll x,ll y){while(x <= n){tree[x] += y;x += lowbit(x);} }inline ll query(ll x){ll ans = 0;while(x){ans += tree[x];x -= lowbit(x);}return ans; }int main(){n in; m in;for(int i=1;i<=n;i++){ll now; now in;add(i,now - last);last = now;}while(m --){ll que; que in;if(que == 1){ll x,y,z;x in; y in; z in;add(x,z);add(y + 1,-z);}else if(que == 2){ll x;x in;printf("%d\n",query(x));}} }//COYG

轉載于:https://www.cnblogs.com/ars4me/p/7536171.html

總結

以上是生活随笔為你收集整理的【模板】树状数组2的全部內容，希望文章能夠幫你解決所遇到的問題。

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