啊哈磊_编程从这里起步

标题: 线段树求和 [打印本页]

作者: 啊哈磊 时间: 2017-10-9 21:02
标题: 线段树求和
[mw_shl_code=c,true]#include <cstdio>
struct Tree
{
int l, r;
long long sum;
} tr[1024000];
int a[1024000];
void Build_Tree ( int x , int y , int i )
{
tr.l = x;
tr.r = y;
if( x == y )tr.sum = a[x] ; //找到叶子节点，赋值
else
{
      int mid = (tr.l + tr.r ) / 2 ;
      Build_Tree ( x , mid , i * 2); //左子树
      Build_Tree ( mid + 1 , y , i * 2 + 1); //右子树
      tr.sum = tr[i * 2].sum + tr[i * 2 + 1].sum; //回溯维护区间和
}
}

long long Query_Tree ( int q , int w , int i )
{
if ( q <= tr.l && w >= tr.r ) return tr.sum; //当前结点的区间完全被目标区间包含
else
{
      long long mid = (tr.l + tr.r) / 2;
      if( q > mid ) //完全在左儿子
      {
         return Query_Tree ( q , w , i * 2 + 1);
      }
      else if (w <= mid ) //完全在右儿子
      {
         return Query_Tree ( q , w , i * 2);
      }
      else //目标区间在左右都有分布
      {
         return Query_Tree ( q , w , i * 2) + Query_Tree ( q , w , i * 2 + 1 );
      }
}
}
int main ( )
{
int N, M, q, val, l, r;
scanf("%d", &N);
for ( int i = 1 ; i <= N ; i++ )scanf("%d", &a);
Build_Tree ( 1 , N , 1);
scanf("%d%d", &l, &r);
         printf("%lld\n", Query_Tree ( l , r, 1 ));

return 0 ;
}[/mw_shl_code]

作者: 啊哈磊 时间: 2017-10-9 21:10
struct Tree
{
int l, r;
long long sum;
} tr[1024000];
void Build_Tree ( int x , int y , int i )
{
tr.l = x;
tr.r = y;
if( x == y )tr.sum = a[x] ; //找到叶子节点，赋值
else
{
      ll mid = (tr.l tr.r ) / 2 ;
      Build_Tree ( x , mid , i * 2); //左子树
      Build_Tree ( mid + 1 , y , i * 2 + 1); //右子树
      tr.sum = tr[i * 2].sum + tr[i * 2 + 1].sum; //回溯维护区间和
}
}

void Update_Tree ( int q , int val , int i )
{
if(tr.l == q && tr.r == q) //找到需要修改的叶子节点
{
      tr.sum = val ; //更新当前结点
}
else //当前结点是非叶子结点
{
      long long mid = (tr.l tr.r ) / 2 ; //取中间
      if ( q <= mid ) //目标节点在左儿子中
      {
         Update_Tree ( q , val , i * 2 );
      }
      else if( q > mid ) //目标节点在右儿子中
      {
         Update_Tree ( q , val , i * 2 + 1 );
      }
      tr.sum = tr[i * 2].sum + tr[i * 2 + 1].sum; //回溯
}
}

long long Query_Tree ( int q , int w , int i )
{
if ( q <= tr.l && w >= tr.r ) return tr.sum; //当前结点的区间完全被目标区间包含
else
{
      long long mid = (tr.l tr.r) / 2;
      if( q > mid ) //完全在左儿子
      {
         return Query_Tree ( q , w , i * 2 + 1);
      }
      else if (w <= mid ) //完全在右儿子
      {
         return Query_Tree ( q , w , i * 2);
      }
      else //目标区间在左右都有分布
      {
         return Query_Tree ( q , w , i * 2) + Query_Tree ( q , w , i * 2 + 1 );
      }
}
}

int main ( )
{

int N, M, q, val, l, r;
scanf("%d", &N);
for ( int i = 1 ; i <= N ; i++ )scanf("%d", &a);
Build_Tree ( 1 , N , 1);
cin >> M ;
while (M--)
{
      int op ;
      cin >> op ;
      if ( op == 1 )
      {
         scanf("%d%d", &q, &val);
         Update_Tree ( q , val , 1);
      }
      else
      {
         scanf("%d%d", &l, &r);
         printf("%lld\n", Query_Tree ( l , r, 1 ));
      }
}
return 0 ;
}

http://www.cnblogs.com/JVxie/p/4854719.html
http://www.cnblogs.com/shadowland/p/5870339.html

作者: 4399APPLE 时间: 2017-10-14 11:18
表示 zkw 线段树大法好啦
常数小到上天
1s 下普通线段树递归 n=10^6 就挂了
作者: 啊哈磊 时间: 2017-10-16 18:36
[mw_shl_code=c,true]#include <cstdio>
struct Tree
{
int l, r;
long long sum;
} tr[1024000];
int a[1024000];
void Build_Tree ( int x , int y , int i )
{
tr.l = x;
tr.r = y;
if( x == y ) tr.sum = a[x] ; //找到叶子节点，赋值
else
{
      int mid = (tr.l + tr.r ) / 2 ;
      Build_Tree ( x , mid , i * 2); //左子树
      Build_Tree ( mid + 1 , y , i * 2 + 1); //右子树
      tr.sum = tr[i * 2].sum + tr[i * 2 + 1].sum; //回溯维护区间和
}
}

long long Query_Tree ( int q , int w , int i )
{
if ( q <= tr.l && w >= tr.r ) return tr.sum; //当前结点的区间完全被目标区间包含
else
{
      long long mid = (tr.l + tr.r) / 2;
      if( q > mid ) //完全在左儿子
      {
         return Query_Tree ( q , w , i * 2 + 1);
      }
      else if (w <= mid ) //完全在右儿子
      {
         return Query_Tree ( q , w , i * 2);
      }
      else //目标区间在左右都有分布
      {
         return Query_Tree ( q , w , i * 2) + Query_Tree ( q , w , i * 2 + 1 );
      }
}
}

void Update_Tree ( int q , int val , int i )
{
if(tr.l == q && tr.r == q) //找到需要修改的叶子节点
{
      tr.sum += val ; //更新当前结点
}
else //当前结点是非叶子结点
{
      long long mid = (tr.l + tr.r ) / 2 ; //取中间

      if ( q <= mid ) //目标节点在左儿子中
      {
         Update_Tree ( q , val , i * 2 );
      }
      else if( q > mid ) //目标节点在右儿子中
      {
         Update_Tree ( q , val , i * 2 + 1 );
      }
      tr.sum = tr[i*2].sum + tr[i*2+1].sum; //回溯
}
}
int main ( )
{
int N, M, q, val, l, r;
scanf("%d", &N);
for ( int i = 1 ; i <= N ; i++ )
scanf("%d", &a);
Build_Tree ( 1 , N , 1);
scanf("%d",&M);
while (M--)
{
      int op ;
      scanf("%d",&op);
      if ( op == 1 )
      {
         scanf("%d%d", &q, &val);
         Update_Tree ( q , val , 1);
      }
      else
      {
         scanf("%d%d", &l, &r);
         printf("%lld\n", Query_Tree ( l , r, 1 ));
      }
}
return 0 ;
}

[/mw_shl_code]

作者: 啊哈磊 时间: 2017-10-16 18:36
给你n个数，有两种操作：
1：给第i个数的值增加X
2：询问区间[a,b]的总和是什么？
输入描述
输入文件第一行为一个整数n，接下来是n行n个整数，表示格子中原来的整数。接下一个正整数q，再接
下来有q行，表示q个询问，第一个整数表示询问代号，询问代号1表示增加，后面的两个数x和A表示给
位置X上的数值增加A，询问代号2表示区间求和，后面两个整数表示a和b，表示要求[a,b]之间的区间和。

样例输入
4
7 6 3 5
2
1 1 4
2 1 2

样例输出
17

数据范围

1 <= n,q <= 100000
作者: 啊哈磊 时间: 2017-10-16 18:38

4399APPLE 发表于 2017-10-14 11:18
表示 zkw 线段树大法好啦
常数小到上天
1s 下普通线段树递归 n=10^6 就挂了

没错一直忘记问你你是哪个省份的现在是高中生还是大学生了?
作者: 4399APPLE 时间: 2017-10-17 12:00

啊哈磊发表于 2017-10-16 18:38
没错一直忘记问你你是哪个省份的现在是高中生还是大学生了?

GD 初三蒟蒻
作者: 4399APPLE 时间: 2017-10-17 12:05

啊哈磊发表于 2017-10-16 18:38
没错一直忘记问你你是哪个省份的现在是高中生还是大学生了?

补充一下
未进队
以前那个 for noi 是某学长搞的

欢迎光临啊哈磊_编程从这里起步 (https://bbs.codeaha.com/) Powered by Discuz! X3.2