【題目鏈接】
ybt 1547：【 例 1】區間和
【題目考點】
1. 線段樹
2. 樹狀數組
【解題思路】
本題要求維護區間和，實現單點修改、區間查詢。
解法1：線段樹
線段樹原理，及實現方法見：洛谷 P3374 【模板】樹狀數組 1（線段樹解法）
解法2：樹狀數組
本題也可以使用樹狀數組完成，知識點及實現方法見：洛谷 P3374 【模板】樹狀數組 1（樹狀數組解法）。
由于都是模板題，大同小異，本文不再進行詳細解釋。
【題解代碼】
解法1：線段樹
#include<bits/stdc++.h>
using namespace std;
#define N 100005
struct Node
{int l, r, m;long long val;
} tree[4*N];
int n, m;
void pushUp(int i)
{tree[i].val = tree[2*i].val+tree[2*i+1].val;
}
void build(int i, int l, int r)
{tree[i].l = l, tree[i].r = r, tree[i].m = (l+r)/2;if(l == r){tree[i].val = 0;return;}build(2*i, l, tree[i].m);build(2*i+1, tree[i].m+1, r);pushUp(i);
}
void update(int i, int x, int v)//a[x] += v
{if(tree[i].l == tree[i].r){tree[i].val += v;return;}if(x <= tree[i].m)update(2*i, x, v);elseupdate(2*i+1, x, v);pushUp(i);
}
long long query(int i, int l, int r)
{if(l <= tree[i].l && tree[i].r <= r)return tree[i].val;long long s = 0;if(l <= tree[i].m)s += query(2*i, l, r);if(r > tree[i].m)s += query(2*i+1, l, r);return s;
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int k, x, y;cin >> n >> m;build(1, 1, n);while(m--){cin >> k >> x >> y;if(k == 0)update(1, x, y);elsecout << query(1, x, y) << '\n';}return 0;
}
解法2：樹狀數組
#include <bits/stdc++.h>
using namespace std;
#define N 100005
long long tree[N], n, m;//tree：樹狀數組
int lowbit(int x)
{return x & -x;
}
void update(int i, long long v)//a[i] += v 單點修改
{for(int x = i; x <= n; x += lowbit(x))tree[x] += v;
}
long long sum(int i)//求a[1]+...+a[i] 區間查詢
{long long s = 0;for(int x = i; x > 0; x -= lowbit(x))s += tree[x];return s;
}
long long query(int l, int r)//求a序列區間和[l, r]
{return sum(r)-sum(l-1);
}
int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);long long a, k, b;cin >> n >> m;for(int i = 1; i <= m; ++i){cin >> k >> a >> b;if(k == 0)update(a, b);elsecout << query(a, b) << '\n'; }return 0;
}
)
)
