一维树状数组BIT

#include<iostream> #include<cstdio> using namespace std; const int maxn = 107; int D[maxn]; int Bit[maxn]; int n; //Bit[i]中存储的是i和前头共(i&-i)个数字 //实现求sum和D[i]+=x的操作 int sum(int i) { int ret = 0; while (i) { ret += Bit[i]; i -= (i&-i); } return ret; } void add(int i, int x) { while (i <= n) { Bit[i] += x; i += (i&-i); } } void show() { cout << "show the awrry:" << endl; for (int i = 1; i <= n; i++) { if (i != 1) cout << " "; cout << D[i]; } cout << endl; } int main() { memset(Bit, 0, sizeof(Bit)); ios::sync_with_stdio(false); cout << "please input n" << endl; cin >> n; cout << "please input " << n << "nums" << endl; for (int i = 1; i <= n; i++) { cin >> D[i]; } for (int i = 1; i <= n; i++) { add(i, D[i]); } cout << "please input q" << endl; int q; cin >> q; cout << "please input q id and x" << endl; for (int i = 0; i<q; i++) { int id, x; cin >> id >> x; D[id] += x; add(id, x); } show(); cout << "please ask quesions:" << endl; while (true) { int x; cin >> x; if (x == -1) { break; } if (x <= n) cout << sum(x) << endl; } return 0; }