497
算法訓練-線段樹
WIKIOI-1080 線段樹練習
題目描述 Description
一行N個方格，開始每個格子裏都有一個整數。現在動態地提出一些問題和修改：提問的形式是求某一個特定的子區間[a,b]中所有元素的和；
修改的規則是指定某一個格子x，加上或者減去一個特定的值A。現在要求你能對每個提問作出正確的回答。1≤N<100000，,提問和修改的總數
m<10000條。
輸入描述 Input Description
輸入文件第一行為一個整數N，接下來是n行n個整數，表示格子中原來的整數。接下一個正整數m，再接下來有m行，表示m個詢問，第一個整數
表示詢問代號，詢問代號1表示增加，後麵的兩個數x和A表示給位置X上的數值增加A，詢問代號2表示區間求和，後麵兩個整數表示a和b，表示
要求[a,b]之間的區間和。
輸出描述 Output Description
共m行，每個整數
樣例輸入 Sample Input
6
4 5 6 2 1 3
4
1 3 5
2 1 4
1 1 9
2 2 6
樣例輸出 Sample Output
22
22
數據範圍及提示 Data Size & Hint
1≤N≤100000， m≤10000 。
本題的目的是訓練線段樹的構造
AC代碼：
#include<stdio.h>
#include<string.h>
struct node//構造線段樹需要的結構體
{
int l,r;
int sum;
}a[400010];//線段樹需要開2*N以上的空間，此處最容易出錯！！
void Bulid(int n,int l,int r)//創建一顆範圍為[l,r]的線段樹
{
a[n].l=l;//左邊界賦值
a[n].r=r;//右邊界賦值
a[n].sum=0;//總和初始化
if(l==r)//如果左右孩子相等,創建結束
return;
Bulid(2*n,l,(l+r)/2);//創建左孩子
Bulid(2*n+1,(l+r)/2+1,r);//創建右孩子
}
void Insert(int n,int v,int num)//向線段樹插入位置為v的權值num
{
a[n].sum+=num;//更新總和
if(a[n].l==a[n].r)//若左右邊界相等，結束更新
return;
if(v<=(a[n].l+a[n].r)/2)//位置小於中間值，往左子樹插入，反之去右子樹
Insert(n*2,v,num);
else
Insert(n*2+1,v,num);
}
void Change(int n,int v,int num)//改變線段樹中位置為v的權值（加上num）
{
if(v==a[n].l&&v==a[n].r)//左右子樹相同，執行更新
{
a[n].sum+=num;
return;
}
else
if(v<=(a[n].l+a[n].r)/2)//位置小於中間值，往左子樹更新，反之去右子樹
Change(n*2,v,num);
else
Change(n*2+1,v,num);
a[n].sum=a[n*2].sum+a[n*2+1].sum;//由於上麵的遞歸已經修改了權值，更新總值
}
int Sum(int n,int l,int r)//計算位置範圍在l、r內數權值的總和
{
if(l==a[n].l&&r==a[n].r)//邊界等於左右子樹，輸出本位置的權值和
return a[n].sum;
if(r<=(a[n].l+a[n].r)/2)//右邊界小於中間值，往左子樹尋找總和
return Sum(n*2,l,r);
else
if(l>(a[n].l+a[n].r)/2)//左邊界大於中間值，往右子樹尋找總和
return Sum(n*2+1,l,r);
else//不滿足上麵兩個條件，i、r則在 a[n].l與a[n].r中間，那麼分別求和
return Sum(n*2,l,(a[n].l+a[n].r)/2)+Sum(n*2+1,(a[n].l+a[n].r)/2+1,r);
}
int main()
{
int i,j,n,m,Q,L,R;
scanf("%d",&n);
Bulid(1,1,n);
for(i=1;i<=n;i++)
{
scanf("%d",&m);
Insert(1,i,m);
}
scanf("%d",&m);
while(m--)
{
scanf("%d %d %d",&Q,&L,&R);
if(Q==1)
{
Change(1,L,R);
}
else if(Q==2)
{
printf("%d\n",Sum(1,L,R));
}
}
return 0;
}
本代碼為原創，轉載請注明出處！
最後更新：2017-04-03 12:55:38