上课时候的笔记。仅供参考。
建树时dfs找到叶子节点再回溯求和。
求区间最值可能需要在Tree结构体中加入
long long max;
接下来是完整的求区间和的线段树。标准的用空间换时间。
1 #include2 3 struct Tree { 4 int l, r; 5 long long sum; 6 } tr[1024000]; 7 int a[1024000]; 8 9 void Build_Tree ( int x , int y , int i ) {10 tr[i].l = x;11 tr[i].r = y;12 if( x == y ) tr[i].sum = a[x] ; //找到叶子节点，赋值13 else {14 int mid = (tr[i].l + tr[i].r ) / 2 ;15 Build_Tree ( x , mid , i * 2); //左子树16 Build_Tree ( mid + 1 , y , i * 2 + 1); //右子树17 tr[i].sum = tr[i * 2].sum + tr[i * 2 + 1].sum; //回溯维护区间和18 }19 }20 21 long long Query_Tree ( int q , int w , int i ) {22 if ( q <= tr[i].l && w >= tr[i].r ) return tr[i].sum; //当前结点的区间完全被目标区间包含23 else {24 long long mid = (tr[i].l + tr[i].r) / 2;25 if( q > mid ) { //完全在左儿子26 return Query_Tree ( q , w , i * 2 + 1);27 } else if (w <= mid ) { //完全在右儿子28 return Query_Tree ( q , w , i * 2);29 } else { //目标区间在左右都有分布30 return Query_Tree ( q , w , i * 2) + Query_Tree ( q , w , i * 2 + 1 );31 }32 }33 }34 35 void Update_Tree ( int q , int val , int i ) {36 if(tr[i].l == q && tr[i].r == q) { //找到需要修改的叶子节点37 tr[i].sum += val ; //更新当前结点38 } else { //当前结点是非叶子结点39 long long mid = (tr[i].l + tr[i].r ) / 2 ; //取中间40 41 if ( q <= mid ) { //目标节点在左儿子中42 Update_Tree ( q , val , i * 2 );43 } else if( q > mid ) { //目标节点在右儿子中44 Update_Tree ( q , val , i * 2 + 1 );45 }46 tr[i].sum = tr[i*2].sum + tr[i*2+1].sum; //回溯47 }48 }49 50 int main ( ) {51 int N, M, q, val, l, r;52 scanf("%d", &N);53 for ( int i = 1 ; i <= N ; i++ )54 scanf("%d", &a[i]);55 Build_Tree ( 1 , N , 1);56 scanf("%d",&M);57 while (M--) {58 int op ;59 scanf("%d",&op);60 if ( op == 1 ) {61 scanf("%d%d", &q, &val);62 Update_Tree ( q , val , 1);63 } else {64 scanf("%d%d", &l, &r);65 printf("%lld\n", Query_Tree ( l , r, 1 ));66 }67 }68 return 0 ;69 }
posted on 2017-10-12 23:06 阅读( ...) 评论( ...) 收藏