在java中添加两个大数组的元素

我必须想出一个算法，它添加了两个大数组的元素（每个数组的大小是10⁹整数，可以达到10⁹）。在java中声明两个大小为10⁹的数组时，我得到一个内存exception！问题陈述： http ： //bit.ly/1XWbUca

通过分析输入约束，您可以看到，如果使用两个整数数组实现解决方案，则在最坏的情况下可以获得2 * 10 ^ 5 * 10 ^ 9数组访问。所以这种方法不行。如果你以某种方式解决你的MLE错误，你几乎肯定会得到TLE。

还有另一种方式……还有另一种选择:)

你只有200k的操作，这意味着，你只需要注意2 * 200k点（对于每个操作你有开始和结束索引）。如果将操作保持在已排序的对数组中，其中ind是开始或结束操作的索引，并且值对于起始索引为正，对于结束索引为负。

回答查询可以通过循环遍历该数组并保持一个sum变量来为你遇到的每个ind，value对添加一个值。

虽然这种方法稍微好一点，因为它可以在O（1）中向数组的段添加值，但在最坏的情况下仍然需要O（n）进行查询。

所以，我想自定义分段树实现是解决这个问题的方法。

我不太了解它，但你可以查一查。

基本上，段树将所有段存储在树状数据结构中，这意味着元素/段的访问和删除需要O（log n）时间……这很好。在这种情况下，分段将是特定操作的范围（起始索引，结束索引）。树的每个节点还将保留应添加到该段的值。

并且您将为两个arrays都有一个分段树。

由于我不知道我在说什么，你可以检查一下那个人。