由于C++语言的高效性与便利性,在进行一些算法设计的时候我总是会选择用C++。其中我遇到过的一个错误让我印象深刻。这是一个关于线段树和运算符优先级的故事。
基本的递归式的线段树看起来大致像这样:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1000001;
struct Node
{
int l, r;
} node[N * 4];
void build( int i, int l, int r )
{
node[i].l = l, node[i].r = r;
if ( l == r ) return ;
int mid = ( l + r ) / 2;
build( i * 2, l, mid );
build( i * 2 + 1, mid + 1, r );
}
int main ()
{
build( 1, 1, N - 1 );
return 0;
}
当然,node结点中你会添加上你需要维护的变量,例如sum、max、min等各种稀奇古怪的东西,这里不做讨论。
但是,一个很明显的问题就是:结点的数量往往很多,动辄几百万,还是递归形式的。而改成非递归显得有点难。考虑到其中有大量的乘法运算,于是我写出了如下改进的代码:
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N = 1000001;
struct Node
{
int l, r;
} node[N << 2];
void build( int i, int l, int r )
{
node[i].l = l, node[i].r = r;
if ( l == r ) return ;
int mid = l + r >> 1;
build( i << 1, l, mid );
build( i << 1 + 1, mid + 1, r );
}
int main ()
{
build( 1, 1, N - 1 );
return 0;
}
用移位运算符来代替乘除法,貌似是个不错的选择。但是这组程序却无法通过测试用例。
通过跟踪建树过程,发现原因是移位运算符 << 的优先级要低于 +。
所以 build( i << 1 + 1, mid + 1, r ); 其实是 build( i << ( 1 + 1 ), mid + 1, r );
而我本意则是 build( ( i << 1 ) + 1, mid + 1, r );
原来加括号很重要!尤其是当你不知道优先级的时候。
但是当你知道了优先级以后,你可能会写出更加优雅、快速的代码:
build( i << 1 | 1, mid + 1, r );
原来,优先级很重要!
原文链接: https://www.cnblogs.com/huoxiayu/p/5250907.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/229839
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!