×
通过社交网站直接登录
×
条@我的评论,查看@我
条新私信,查看私信
条新评论,查看评论
位新粉丝 查看粉丝
数学天地 高等数学 选择题 思维
于 2017-04-12 00:40提供
一般
(26)

区间[1,n]内有n个数字。现在按顺序进行n次操作,操作有以下两种:

1.给你三个整数L,R,K。把[L,R]的数字都修改成k

2.给你两个整数L,R。询问[L,R]的数字之和

对于所有的L,R,K,有

1<=L<=R<=n

k为整数,且绝对值小于10的9次方

访问或修改一个数字需要消耗1个单位的时间

现在要求设计一种效率尽可能高的算法来正确回答所有的操作2。

效率高的算法要求随着n规模增长,所花时间T的增长尽可能慢。

如T与n^2成正比的算法,效率就要低于T与n成正比的算法。

那么最优情况下,T与下列哪个选项成正比?

提示:可以使用额外的空间来记录信息。

标签: 效率 操作 数字
4
答案:
解析:
20
收藏