增加两个大阵列的Java元素 [英] Adding elements of two big arrays in java
问题描述
我要拿出一个算法，增加了两个大数组（每个数组的大小是一个整数，可以上升到10⁹的10⁹）的元素。 在声明两个数组在Java中10⁹各大小，我得到一个内存异常！ 问题陈述： http://bit.ly/1XWbUca
I have to come up with an algorithm that adds elements of two big arrays(size of each array is 10⁹ of integers that can go up to 10⁹). When declaring two arrays in java with size of 10⁹ each, I get a memory exception! The problem statement: http://bit.ly/1XWbUca
推荐答案
通过分析输入的限制，你可以看到你可以在最坏的情况下，2 * 10 ^ 5 * 10 ^ 9数组访问，如果你使用实施解决方案两个数组整数的。这样的做法是不行的。如果你以某种方式解决你的最大似然估计的错误，你几乎肯定会得到TLE。
by analyzing the input constraints you can see that you can get 2*10^5 * 10^9 array accesses in the worst case if you implement the solution using two arrays of ints. So that approach will not do. If you somehow solve your MLE error, you will almost certainly get TLE.
还有一个办法......还有另一个选择：）
There is another way... there is another option :)
您只需要200K的操作，这意味着，你只需要关注2 * 20万点（你有开始和结束索引每一个操作）。 如果你把你的操作对，其中IND的开始或结束经营和价值指数的排序阵列中是积极的开始索引和负结束索引。
you only have 200k operations, that means, you only have to pay attention to 2*200k points (for each operation you have start and end index). If you keep your operations in the sorted array of pairs , where ind is starting or ending index of operation and value is positive for starting index and negative for ending index.
回答的查询可以通过该数组循环，并保持一个总和变量，它为每个IND添加值，你遇到值对来完成。
Answering the query can be done by looping through that array and keeping a sum variable to which you add a value for each ind,value pair you encounter.
虽然这种方法是略好，因为它可以将值添加到O型数组的段（1）它仍然需要为O（n），在最坏的情况下查询。
While that approach is marginally better, because it can add a value to the segment of an array in O(1) it still requires O(n) for queries in the worst case.
所以，我想自定义段树的实施就是为了解决这一个办法。
So, I imagine the custom segment tree implementation is the way to solve this one.
我不很了解，但你可以看看它。
I don't know much about it, but you can look it up.
基本上，段树将存储您在一个树状的数据结构，这意味着元素的访问，并删除所有段/网段需要O（log n）的时间......这是很好的。在这种情况下，节段将是特定的操作（开始索引，结束索引）的范围内。树的每个节点也将保持一个值，你应该添加到该段。
Basically, segment tree will store all your segments in a tree-like data structure, that means the access and deletion of elements/segments takes O(log n) time... which is good. Segments in this case would be the range of particular operation (start index, end index). Each node of the tree would also keep a value that you should add to that segment.
和你将有一个段树两个数组。
And you would have one segment tree for both arrays.
Since I don't know what I'm talking about, you can check someone who does.
这篇关于增加两个大阵列的Java元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
