Can someone help me with 2D/3D segment treesHow can I upload files asynchronously?How can I merge properties of two JavaScript objects dynamically?How can I convert a string to boolean in JavaScript?How can I know which radio button is selected via jQuery?How can I get query string values in JavaScript?How can I pretty-print JSON using JavaScript?How can I refresh a page with jQuery?Ukkonen's suffix tree algorithm in plain EnglishImage Processing: Algorithm Improvement for 'Coca-Cola Can' RecognitionCan (a== 1 && a ==2 && a==3) ever evaluate to true?
Hai la patente? - omission of possessive adjective
E: Sub-process /usr/bin/dpkg returned an error code (1) - but how do I find the meaningful error messages in APT's output?
How to compare two different formulations of a problem?
Sleeping solo in a double sleeping bag
Chess software to analyze games
My two team members in a remote location don't get along with each other; how can I improve working relations?
Can a Beast Master ranger choose a swarm as an animal companion?
Nuclear decay triggers
Changing a TGV booking
Can I submit a paper under an alias so as to avoid trouble in my country?
Repurpose telephone line to ethernet
Why didn’t Doctor Strange stay in the original winning timeline?
How much code would a codegolf golf if a codegolf could golf code?
Do predators tend to have vertical slit pupils versus horizontal for prey animals?
Is it allowable to use an organization's name to publish a paper in a conference, even after I graduate from it?
How to decide whether an eshop is safe or compromised
Why doesn't the Falcon-9 first stage use three legs to land?
Is there any road between the CA State Route 120 and Sherman Pass Road (Forest Route 22S0) that crosses Yosemite/Serria/Sequoia National Park/Forest?
How did Apollo 15's depressurization work?
Does the Symbiotic Entity damage apply to a creature hit by the secondary damage of Green Flame Blade?
Is it appropriate for a business to ask me for my credit report?
Alchemist potion on Undead
Using は before 欲しい instead が
Why doesn't mathematics collapse down, even though humans quite often make mistakes in their proofs?
Can someone help me with 2D/3D segment trees
How can I upload files asynchronously?How can I merge properties of two JavaScript objects dynamically?How can I convert a string to boolean in JavaScript?How can I know which radio button is selected via jQuery?How can I get query string values in JavaScript?How can I pretty-print JSON using JavaScript?How can I refresh a page with jQuery?Ukkonen's suffix tree algorithm in plain EnglishImage Processing: Algorithm Improvement for 'Coca-Cola Can' RecognitionCan (a== 1 && a ==2 && a==3) ever evaluate to true?
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
0
I'm trying to solve the task:
Given a function. One of the function arguments is an array. It could be 1 dimensional/ 2 dimensional or 3 dimensional.
The rest ones params are: sum function and neutral number. Will be 0.
I need to build the segment tree (1D / 2D / 3D), depending on incoming array and calculate the range sum.
Can someone give me a hint?
I wrote a function that builds the 2D segment tree. Code below:
function recursiveSegmentTree(array, fn, N)
var t = new Array(array.length * 16);
//Building X2D segment tree
function build_Y(vx, lx, rx, vy, ly, ry, array)
if (ly == ry)
if (lx == rx)
t[vx][vy] = array[lx][ly];
else
t[vx][vy] = fn(t[2 * vx][vy], t[2 * vx + 1][vy]);
else
let vmiddleY = Math.floor((ry + ly) / 2);
build_Y(vx, lx, rx, 2 * vy, ly, vmiddleY, array);
build_Y(vx, lx, rx, 2 * vy + 1, vmiddleY + 1, ry, array);
t[vx][vy] = fn(t[vx][2 * vy], t[vx][2 * vy + 1]);
function build_X(vx, lx, rx, array)
if (lx != rx)
let vmiddleX = Math.floor((rx + lx) / 2);
build_X(2 * vx, lx, vmiddleX, array);
build_X(2 * vx + 1, vmiddleX + 1, rx, array);
build_Y(vx, lx, rx, 1, 0, array.length - 1, array);
//Calculating sum
function finalQuery(pos, start, end, x1, x2, node, array, N)
if (x2 < start
function query(pos, start, end, y1, y2, x1, x2, array, N)
for (let i = 0; i < (array.length * 16); i++)
t[i] = new Array(array.length * 16);
return function (from, to) array.length < to)
throw new Error("Out of range");
if (to < from)
throw new Error("From is greater");
if (from == to) return N;
let result = N;
if (Array.isArray(array[0]) == false)
array.slice(from, to).forEach((arr) =>
if (!Array.isArray(arr))
result += arr;
else
result += fn(result, arr);
);
else if (Array.isArray(array[0]) == true)
build_X(1, 0, array.length - 1, array);
console.log(t);
result = query(1, 0, array.length - 1, from, to - 1, from, to - 1, array, N);
return result;
;
;
javascript algorithm segment-tree
edited Mar 27 at 14:59
ilim
3,5697 gold badges17 silver badges36 bronze badges
asked Mar 27 at 14:51
AleksandrAleksandr
64 bronze badges
|
show 1 more comment
0
I'm trying to solve the task:
Given a function. One of the function arguments is an array. It could be 1 dimensional/ 2 dimensional or 3 dimensional.
The rest ones params are: sum function and neutral number. Will be 0.
I need to build the segment tree (1D / 2D / 3D), depending on incoming array and calculate the range sum.
Can someone give me a hint?
I wrote a function that builds the 2D segment tree. Code below:
function recursiveSegmentTree(array, fn, N)
var t = new Array(array.length * 16);
//Building X2D segment tree
function build_Y(vx, lx, rx, vy, ly, ry, array)
if (ly == ry)
if (lx == rx)
t[vx][vy] = array[lx][ly];
else
t[vx][vy] = fn(t[2 * vx][vy], t[2 * vx + 1][vy]);
else
let vmiddleY = Math.floor((ry + ly) / 2);
build_Y(vx, lx, rx, 2 * vy, ly, vmiddleY, array);
build_Y(vx, lx, rx, 2 * vy + 1, vmiddleY + 1, ry, array);
t[vx][vy] = fn(t[vx][2 * vy], t[vx][2 * vy + 1]);
function build_X(vx, lx, rx, array)
if (lx != rx)
let vmiddleX = Math.floor((rx + lx) / 2);
build_X(2 * vx, lx, vmiddleX, array);
build_X(2 * vx + 1, vmiddleX + 1, rx, array);
build_Y(vx, lx, rx, 1, 0, array.length - 1, array);
//Calculating sum
function finalQuery(pos, start, end, x1, x2, node, array, N)
if (x2 < start
function query(pos, start, end, y1, y2, x1, x2, array, N)
for (let i = 0; i < (array.length * 16); i++)
t[i] = new Array(array.length * 16);
return function (from, to) array.length < to)
throw new Error("Out of range");
if (to < from)
throw new Error("From is greater");
if (from == to) return N;
let result = N;
if (Array.isArray(array[0]) == false)
array.slice(from, to).forEach((arr) =>
if (!Array.isArray(arr))
result += arr;
else
result += fn(result, arr);
);
else if (Array.isArray(array[0]) == true)
build_X(1, 0, array.length - 1, array);
console.log(t);
result = query(1, 0, array.length - 1, from, to - 1, from, to - 1, array, N);
return result;
;
;
javascript algorithm segment-tree
edited Mar 27 at 14:59
ilim
3,5697 gold badges17 silver badges36 bronze badges
asked Mar 27 at 14:51
AleksandrAleksandr
64 bronze badges
do you have some examples of input and output?
– Nina Scholz
Mar 27 at 14:54
Well if you have no updates you can do 1/2/3D queries using prefix sums in O(1) per query, if you do have point updates you can do same thing using Fenwick (a.k.a. Binary Indexed Tree) tree which is way easier to extend to higher dimensions. Segment tree seems over-complex for simple sum queries
– Photon
Mar 27 at 15:01
@Nina Scholz Sure, the test system will give the following info: let 2Darray = [[1, 0, 1, 1], [0, 1, 0, 0],[0, 0, 0, 1], [1, 1, 1, 1] ]. let tree = recursiveSegmentTree(array, sum, 0); expect(tree(0, 1)(0, 1)).toBe(1); expect(tree(0, 1)(1, 2)).toBe(0); expect(tree(3, 4)(3, 4)).toBe(1);
– Aleksandr
Mar 27 at 15:02
@Photon, No, only sum queries. About "prefix sum...". I'm not following...
– Aleksandr
Mar 27 at 15:04
@Aleksandr well let's say we have 1D Array of N elements (indexing starts at 1). We create another array P, such that P[ i ] = sum of all A[ j ] such that j <= i. Having such array we can get any interval sum in O(1). i.e. for interval [ l, r ] we just use P[ r ] - P[ l - 1] which gives us required sum. Using Inclusion Exclusion we can easily generalize this to higher dimensions.
– Photon
Mar 27 at 15:08
|
show 1 more comment
0
0
0
1
I'm trying to solve the task:
Given a function. One of the function arguments is an array. It could be 1 dimensional/ 2 dimensional or 3 dimensional.
The rest ones params are: sum function and neutral number. Will be 0.
I need to build the segment tree (1D / 2D / 3D), depending on incoming array and calculate the range sum.
Can someone give me a hint?
I wrote a function that builds the 2D segment tree. Code below:
function recursiveSegmentTree(array, fn, N)
var t = new Array(array.length * 16);
//Building X2D segment tree
function build_Y(vx, lx, rx, vy, ly, ry, array)
if (ly == ry)
if (lx == rx)
t[vx][vy] = array[lx][ly];
else
t[vx][vy] = fn(t[2 * vx][vy], t[2 * vx + 1][vy]);
else
let vmiddleY = Math.floor((ry + ly) / 2);
build_Y(vx, lx, rx, 2 * vy, ly, vmiddleY, array);
build_Y(vx, lx, rx, 2 * vy + 1, vmiddleY + 1, ry, array);
t[vx][vy] = fn(t[vx][2 * vy], t[vx][2 * vy + 1]);
function build_X(vx, lx, rx, array)
if (lx != rx)
let vmiddleX = Math.floor((rx + lx) / 2);
build_X(2 * vx, lx, vmiddleX, array);
build_X(2 * vx + 1, vmiddleX + 1, rx, array);
build_Y(vx, lx, rx, 1, 0, array.length - 1, array);
//Calculating sum
function finalQuery(pos, start, end, x1, x2, node, array, N)
if (x2 < start
function query(pos, start, end, y1, y2, x1, x2, array, N)
for (let i = 0; i < (array.length * 16); i++)
t[i] = new Array(array.length * 16);
return function (from, to) array.length < to)
throw new Error("Out of range");
if (to < from)
throw new Error("From is greater");
if (from == to) return N;
let result = N;
if (Array.isArray(array[0]) == false)
array.slice(from, to).forEach((arr) =>
if (!Array.isArray(arr))
result += arr;
else
result += fn(result, arr);
);
else if (Array.isArray(array[0]) == true)
build_X(1, 0, array.length - 1, array);
console.log(t);
result = query(1, 0, array.length - 1, from, to - 1, from, to - 1, array, N);
return result;
;
;
javascript algorithm segment-tree
edited Mar 27 at 14:59
ilim
3,5697 gold badges17 silver badges36 bronze badges
asked Mar 27 at 14:51
AleksandrAleksandr
64 bronze badges
I'm trying to solve the task:
Given a function. One of the function arguments is an array. It could be 1 dimensional/ 2 dimensional or 3 dimensional.
The rest ones params are: sum function and neutral number. Will be 0.
I need to build the segment tree (1D / 2D / 3D), depending on incoming array and calculate the range sum.
Can someone give me a hint?
I wrote a function that builds the 2D segment tree. Code below:
function recursiveSegmentTree(array, fn, N)
var t = new Array(array.length * 16);
//Building X2D segment tree
function build_Y(vx, lx, rx, vy, ly, ry, array)
if (ly == ry)
if (lx == rx)
t[vx][vy] = array[lx][ly];
else
t[vx][vy] = fn(t[2 * vx][vy], t[2 * vx + 1][vy]);
else
let vmiddleY = Math.floor((ry + ly) / 2);
build_Y(vx, lx, rx, 2 * vy, ly, vmiddleY, array);
build_Y(vx, lx, rx, 2 * vy + 1, vmiddleY + 1, ry, array);
t[vx][vy] = fn(t[vx][2 * vy], t[vx][2 * vy + 1]);
function build_X(vx, lx, rx, array)
if (lx != rx)
let vmiddleX = Math.floor((rx + lx) / 2);
build_X(2 * vx, lx, vmiddleX, array);
build_X(2 * vx + 1, vmiddleX + 1, rx, array);
build_Y(vx, lx, rx, 1, 0, array.length - 1, array);
//Calculating sum
function finalQuery(pos, start, end, x1, x2, node, array, N)
if (x2 < start
function query(pos, start, end, y1, y2, x1, x2, array, N)
for (let i = 0; i < (array.length * 16); i++)
t[i] = new Array(array.length * 16);
return function (from, to) array.length < to)
throw new Error("Out of range");
if (to < from)
throw new Error("From is greater");
if (from == to) return N;
let result = N;
if (Array.isArray(array[0]) == false)
array.slice(from, to).forEach((arr) =>
if (!Array.isArray(arr))
result += arr;
else
result += fn(result, arr);
);
else if (Array.isArray(array[0]) == true)
build_X(1, 0, array.length - 1, array);
console.log(t);
result = query(1, 0, array.length - 1, from, to - 1, from, to - 1, array, N);
return result;
;
;
javascript algorithm segment-tree
javascript algorithm segment-tree
edited Mar 27 at 14:59
ilim
3,5697 gold badges17 silver badges36 bronze badges
asked Mar 27 at 14:51
AleksandrAleksandr
64 bronze badges
edited Mar 27 at 14:59
ilim
3,5697 gold badges17 silver badges36 bronze badges
asked Mar 27 at 14:51
AleksandrAleksandr
64 bronze badges
edited Mar 27 at 14:59
ilim
3,5697 gold badges17 silver badges36 bronze badges
edited Mar 27 at 14:59
ilim
3,5697 gold badges17 silver badges36 bronze badges
edited Mar 27 at 14:59
ilim
3,5697 gold badges17 silver badges36 bronze badges
3,5697 gold badges17 silver badges36 bronze badges
asked Mar 27 at 14:51
AleksandrAleksandr
64 bronze badges
asked Mar 27 at 14:51
AleksandrAleksandr
64 bronze badges
asked Mar 27 at 14:51
AleksandrAleksandr
64 bronze badges
64 bronze badges
do you have some examples of input and output?
– Nina Scholz
Mar 27 at 14:54
Well if you have no updates you can do 1/2/3D queries using prefix sums in O(1) per query, if you do have point updates you can do same thing using Fenwick (a.k.a. Binary Indexed Tree) tree which is way easier to extend to higher dimensions. Segment tree seems over-complex for simple sum queries
– Photon
Mar 27 at 15:01
@Nina Scholz Sure, the test system will give the following info: let 2Darray = [[1, 0, 1, 1], [0, 1, 0, 0],[0, 0, 0, 1], [1, 1, 1, 1] ]. let tree = recursiveSegmentTree(array, sum, 0); expect(tree(0, 1)(0, 1)).toBe(1); expect(tree(0, 1)(1, 2)).toBe(0); expect(tree(3, 4)(3, 4)).toBe(1);
– Aleksandr
Mar 27 at 15:02
@Photon, No, only sum queries. About "prefix sum...". I'm not following...
– Aleksandr
Mar 27 at 15:04
@Aleksandr well let's say we have 1D Array of N elements (indexing starts at 1). We create another array P, such that P[ i ] = sum of all A[ j ] such that j <= i. Having such array we can get any interval sum in O(1). i.e. for interval [ l, r ] we just use P[ r ] - P[ l - 1] which gives us required sum. Using Inclusion Exclusion we can easily generalize this to higher dimensions.
– Photon
Mar 27 at 15:08
|
show 1 more comment
do you have some examples of input and output?
– Nina Scholz
Mar 27 at 14:54
Well if you have no updates you can do 1/2/3D queries using prefix sums in O(1) per query, if you do have point updates you can do same thing using Fenwick (a.k.a. Binary Indexed Tree) tree which is way easier to extend to higher dimensions. Segment tree seems over-complex for simple sum queries
– Photon
Mar 27 at 15:01
@Nina Scholz Sure, the test system will give the following info: let 2Darray = [[1, 0, 1, 1], [0, 1, 0, 0],[0, 0, 0, 1], [1, 1, 1, 1] ]. let tree = recursiveSegmentTree(array, sum, 0); expect(tree(0, 1)(0, 1)).toBe(1); expect(tree(0, 1)(1, 2)).toBe(0); expect(tree(3, 4)(3, 4)).toBe(1);
– Aleksandr
Mar 27 at 15:02
@Photon, No, only sum queries. About "prefix sum...". I'm not following...
– Aleksandr
Mar 27 at 15:04
@Aleksandr well let's say we have 1D Array of N elements (indexing starts at 1). We create another array P, such that P[ i ] = sum of all A[ j ] such that j <= i. Having such array we can get any interval sum in O(1). i.e. for interval [ l, r ] we just use P[ r ] - P[ l - 1] which gives us required sum. Using Inclusion Exclusion we can easily generalize this to higher dimensions.
– Photon
Mar 27 at 15:08
do you have some examples of input and output?
– Nina Scholz
Mar 27 at 14:54
do you have some examples of input and output?
– Nina Scholz
Mar 27 at 14:54
Well if you have no updates you can do 1/2/3D queries using prefix sums in O(1) per query, if you do have point updates you can do same thing using Fenwick (a.k.a. Binary Indexed Tree) tree which is way easier to extend to higher dimensions. Segment tree seems over-complex for simple sum queries
– Photon
Mar 27 at 15:01
Well if you have no updates you can do 1/2/3D queries using prefix sums in O(1) per query, if you do have point updates you can do same thing using Fenwick (a.k.a. Binary Indexed Tree) tree which is way easier to extend to higher dimensions. Segment tree seems over-complex for simple sum queries
– Photon
Mar 27 at 15:01
@Nina Scholz Sure, the test system will give the following info: let 2Darray = [[1, 0, 1, 1], [0, 1, 0, 0],[0, 0, 0, 1], [1, 1, 1, 1] ]. let tree = recursiveSegmentTree(array, sum, 0); expect(tree(0, 1)(0, 1)).toBe(1); expect(tree(0, 1)(1, 2)).toBe(0); expect(tree(3, 4)(3, 4)).toBe(1);
– Aleksandr
Mar 27 at 15:02
@Nina Scholz Sure, the test system will give the following info: let 2Darray = [[1, 0, 1, 1], [0, 1, 0, 0],[0, 0, 0, 1], [1, 1, 1, 1] ]. let tree = recursiveSegmentTree(array, sum, 0); expect(tree(0, 1)(0, 1)).toBe(1); expect(tree(0, 1)(1, 2)).toBe(0); expect(tree(3, 4)(3, 4)).toBe(1);
– Aleksandr
Mar 27 at 15:02
@Photon, No, only sum queries. About "prefix sum...". I'm not following...
– Aleksandr
Mar 27 at 15:04
@Photon, No, only sum queries. About "prefix sum...". I'm not following...
– Aleksandr
Mar 27 at 15:04
@Aleksandr well let's say we have 1D Array of N elements (indexing starts at 1). We create another array P, such that P[ i ] = sum of all A[ j ] such that j <= i. Having such array we can get any interval sum in O(1). i.e. for interval [ l, r ] we just use P[ r ] - P[ l - 1] which gives us required sum. Using Inclusion Exclusion we can easily generalize this to higher dimensions.
– Photon
Mar 27 at 15:08
@Aleksandr well let's say we have 1D Array of N elements (indexing starts at 1). We create another array P, such that P[ i ] = sum of all A[ j ] such that j <= i. Having such array we can get any interval sum in O(1). i.e. for interval [ l, r ] we just use P[ r ] - P[ l - 1] which gives us required sum. Using Inclusion Exclusion we can easily generalize this to higher dimensions.
– Photon
Mar 27 at 15:08
|
show 1 more comment
0
active
oldest
votes
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55380191%2fcan-someone-help-me-with-2d-3d-segment-trees%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
0
active
oldest
votes
0
active
oldest
votes
active
oldest
votes
active
oldest
votes
Is this question similar to what you get asked at work? Learn more about asking and sharing private information with your coworkers using Stack Overflow for Teams.
Is this question similar to what you get asked at work? Learn more about asking and sharing private information with your coworkers using Stack Overflow for Teams.
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55380191%2fcan-someone-help-me-with-2d-3d-segment-trees%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
do you have some examples of input and output?
– Nina Scholz
Mar 27 at 14:54
Well if you have no updates you can do 1/2/3D queries using prefix sums in O(1) per query, if you do have point updates you can do same thing using Fenwick (a.k.a. Binary Indexed Tree) tree which is way easier to extend to higher dimensions. Segment tree seems over-complex for simple sum queries
– Photon
Mar 27 at 15:01
@Nina Scholz Sure, the test system will give the following info: let 2Darray = [[1, 0, 1, 1], [0, 1, 0, 0],[0, 0, 0, 1], [1, 1, 1, 1] ]. let tree = recursiveSegmentTree(array, sum, 0); expect(tree(0, 1)(0, 1)).toBe(1); expect(tree(0, 1)(1, 2)).toBe(0); expect(tree(3, 4)(3, 4)).toBe(1);
– Aleksandr
Mar 27 at 15:02
@Photon, No, only sum queries. About "prefix sum...". I'm not following...
– Aleksandr
Mar 27 at 15:04
@Aleksandr well let's say we have 1D Array of N elements (indexing starts at 1). We create another array P, such that P[ i ] = sum of all A[ j ] such that j <= i. Having such array we can get any interval sum in O(1). i.e. for interval [ l, r ] we just use P[ r ] - P[ l - 1] which gives us required sum. Using Inclusion Exclusion we can easily generalize this to higher dimensions.
– Photon
Mar 27 at 15:08