線段樹就是區間的查找，如果區間不是當前線段樹節點的區間，需要劃分為左、右，再遞歸查找

#include <iostream> #include <stdio.h> #include <string>using namespace std;const int maxn = 55555; int a[maxn]; int tree[maxn << 2];//節點數是區間的4倍void pushUp(int curr) {tree[curr] = tree[2*curr] + tree[2*curr+1]; }void buidTree(int left, int right, int curr) {//本節點在數組中的位置是curr;本節點的左邊界是left，右邊界是rightif (left == right) {tree[curr] = a[left];return;}int m = left + (right - left)/2;// if (m >= left)buidTree(left,m,2*curr);// if (m+1<=right)buidTree(m+1,right,2*curr + 1);pushUp(curr);}void update(int p, int add, int left, int right, int curr) {//第p個數，增加add;當前節點是curr,左是left，右是right;先找到p在哪個范圍內,一定要找到精確的小范圍，然后大范圍是由小范圍組合而成if (left == right) {tree[curr] += add;return;}int m = left + (right - left)/2;if (p <= m)update(p,add,left,m,2*curr);elseupdate(p,add,m+1,right,2*curr + 1);pushUp(curr);}int query(int ql, int qr, int currLeft, int currRight, int curr) {//查找區間[ql,qr]if (ql <= currLeft && qr >= currRight) {return tree[curr];}int m = currLeft + (currRight - currLeft)/2;int sum = 0;if (ql <=m)sum = query(ql,qr,currLeft,m,2*curr);if (qr >m)sum += query(ql,qr,m+1,currRight,2*curr+1);return sum; }int main() {int t,n;scanf("%d", &t);for (int i = 0; i < t ; ++i ) {printf("Case %d:\n",i+1);scanf("%d",&n);memset(a,0,sizeof(a));for (int j = 1; j <= n; ++j )scanf("%d",a + j);buidTree(1,n,1);char op[10];while(scanf("%s",&op)) {if (op[0] == 'E')break;int a1,a2;scanf("%d%d",&a1,&a2);if (op[0] == 'Q')printf("%d\n",query(a1,a2,1,n,1));else if(op[0] == 'S')update(a1,-a2,1,n,1);elseupdate(a1,a2,1,n,1);}} }

#include <iostream> #include <stdio.h>using namespace std;const int maxn = 55555; int a[maxn]; int tree[maxn<<2];//線段樹的每一個葉子節點就是a中的元素，還有其他的非葉子節點，應該需要2*maxn+1個元素void pushUp(int ind) {tree[ind] = tree[2*ind] + tree[2*ind+1]; }void buildTree(int left, int right, int ind) {//找到葉子節點相應的位置, ind是這個節點的編號//left 和 right是這個節點所對應的范圍if (left == right) {tree[ind] = a[left];return;}int mid = (left + right)/2;buildTree(left, mid, 2*ind);buildTree(mid+1, right, 2*ind + 1);pushUp(ind);}int query(int beg, int end , int left, int right, int ind){// beg, end是要查詢的區間；left和right是這個節點的范圍if (beg<=left && end >= right)return tree[ind];int mid = (left + right) / 2;int l = 0, r = 0;if (mid >= beg)l = query(beg,end,left,mid, 2*ind);if (mid < end)r = query(beg,end,mid +1,right, 2*ind+1);return l+ r; }void update(int pos, int value, int left, int right, int ind) {if(left == right) {tree[ind] += value;return;}int mid = (left + right) / 2;if (mid >=pos)update(pos, value, left, mid, 2*ind);elseupdate(pos,value, mid + 1, right, 2*ind+1);pushUp(ind); }int main() {int t,n;scanf("%d", &t);for (int i = 0; i < t ; ++i){printf("Case %d:\n", i + 1);scanf("%d", &n);memset(a,0,sizeof(a));for(int j = 1; j <= n; ++j)scanf("%d", a + j);buildTree(1,n, 1);char op[10];while (scanf("%s", op)){if (op[0] == 'E')break;int a1, a2;scanf("%d%d", &a1,&a2);if (op[0] == 'Q')printf("%d\n", query(a1, a2,1,n,1));else if(op[0] == 'S')update(a1,-a2,1,n,1);elseupdate(a1,a2,1,n,1);}} }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的hdu1166 线段树的全部內容，希望文章能夠幫你解決所遇到的問題。

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