The entire ArrayList is updating when I am trying to update one element Java 21

I was doing some algo in my free time and had a weird issue. I can not understand why this is happening. I have two lists, and I am updating elements precisely the same way in both of them, but in the "lazy" list, when I update an element, all elements are updated.

This is the essential part of the code:

public class SegmentTree {

    public static void main(String[] args) {
        List<Integer> a = List.of(1, 2, 3, 4, 5, 6, 7, 8);
        SegmentTreeObject segmentTreeObject = new SegmentTreeObject(a);
        segmentTreeObject.build(a);
        segmentTreeObject.list.forEach(s -> System.out.println(s.leftPosition + " " + s.rightPosition + " " + s.value));
        segmentTreeObject.updateLazy(new Point(0, 7), 5);
        segmentTreeObject.lazy.forEach(s -> System.out.println(s.leftPosition + " " + s.rightPosition + " " + s.value));
    }
}

class SegmentTreeObject {

    List<Node> list;
    List<Integer> original;

    //Lazy tree
    List<Node> lazy;

    int size;

    SegmentTreeObject(List<Integer> obj) {
        this.list = new ArrayList<>(Collections.nCopies(4 * obj.size(), new Node(100, 100, 0)));
        this.lazy = new ArrayList<>(Collections.nCopies(4 * obj.size(), new Node(0, 0, 0)));
        this.original = new ArrayList<>(obj);
        this.size = obj.size();
    }

    void updateLazyTree(int start, int end, int left, int right, int node, int newValue) {
        if(left > end || right < start) {
            return;
        }
        if (start >= left && end <= right) {
            this.list.get(node).updateNode(this.list.get(node).value + (end-start+1) * newValue);
            this.lazy.get(2 * node + 1).updateNode(this.lazy.get(2*node+1).value + newValue);
            this.lazy.get(2 * node + 2).updateNode(this.lazy.get(2*node+2).value + newValue);

            return;
        }

        int mid = start + (end-start) / 2;
        updateLazyTree(start, mid, left, right, 2 * node + 1, newValue);
        updateLazyTree(mid + 1, end, left, right, 2 * node + 2, newValue);
    }

    void updateLazy(Point range, int value) {
        updateLazyTree(0, this.size - 1, range.x, range.y, 0, value);
    }
}

class Node {
    int leftPosition;
    int rightPosition;
    int value;

    // All-args constructor omitted for brevity

    public void updateNode(int value){
        this.value = value;
    }
}

and the output of the lazy is like this:

0 0 10
0 0 10
0 0 10
0 0 10
0 0 10
0 0 10
0 0 10

I have also checked with the debugger, and yes, the "lazy" list is updating the entity after one "updateNode" call.

Thank you for your time!

Please let me know if you have any ideas; I might be wrong in creating the "lazy" list.

>Solution :

Count the new. That’s how many objects you have. Thus, in:

this.list = new ArrayList<>(Collections.nCopies(4*obj.size(),new Node(100,100,0)));

I count.. 1 new.

So, you have a list with loads of entries, but, only one Node object. How can that be? How can you have an arraylist whose .size() reports, in this example case, 32 (obj is 8 big, and you multiply it by 4) – but only one Node object?

Well, imagine this situation:

I build one single house.

I then buy an address book from the store. It has 32 pages. On each and every page I write the same address. The address of that one house I built.

TADA! 32 houses!

Not quite. I have 32 addresses, sure. And they are all the same. 1 house, 32 pages.

The same situation is happening here. You have one node object, and an arraylist with 32 references, all to that one node object. Change one and you change them all, for the exact same reason that if you take that address book with its 32 pages, pick a random page, walk over to the house, toss a brick through the window then: Regardless of which page you open your address book to, if you walk over to the address you find there, guess what? Window’s broken.

You want 32 node objects.

this.list = new ArrayList<>();
for (int i = 0; i < 4 * obj.size()) this.list.add(new Node(100, 100, 0));

If I count the amount of times new is executed now, I end up at 32. Indeed this code will do fine (you’ll also have to fix this.lazy, of course).

If you feel that somehow ruins the cleanliness of it all, well, this method COULD exist in j.u.Collections:

public static <T> nTimes(int n, Supplier<T> supplier) {
  if (n < 0) throw new IllegalArgumentException("" + n);
  var list = new ArrayList<T>(n);
  for (int i = 0; i < n; i++) list.add(supplier.get());
  return list;
}

Then you could call:

Collections.nTimes(4 * obj.size() () -> new Node(100, 100, 0));

But that method simply doesn’t exist. It may never: In large part, nCopies exists at all because it allows quite an impressive optimization: It can represent a million entries with virtually no memory, it just remembers the one reference as well as the number ‘one million’. nCopies is like a magic address book that has only 2 pages, so it’s very small: one page with a single number on it, and a second page with a single address on it. For all purposes this address book acts like it was a big one (as many pages as that first number), with the same address on each of those pages. That doesn’t sound like a very useful address book, and, indeed, nCopies is rarely used. But that’s what its for. If you need this weird ‘address book with LOTS of identical entries’ thing, nCopies is very very good at it.

It’s not at all what you want here, though. So, just write a loop, really.