I think what you are looking for is lazy segment tree + merge sort tree. time complexity is log^2 n per query

sqrt decomposition my beloved ($$$O(\sqrt[]{n}log n)$$$ sol so might be a bit slow)

divide the array into $$$\sqrt[]{n}$$$ segments of length $$$\sqrt[]{n}$$$ (and store them twice, one of them is the sorted version)

add/subtract query would take $$$O(\sqrt[]{n} log n)$$$:

for each block store a value which is how much the entire segment is affected by (we'll call it $$$a_i$$$), if the query affects the entire block then just update $$$a_i$$$

if it only affects it partially, then subtract/add those elements and build the sorted array again

for searching negative numbers -> for partial segments just loop through them, for full segments: binary search to find the number of values smaller than $$$-a_i$$$ (also $$$O(\sqrt[]{n}log n)$$$)

obviously it's not the runtime you're looking for but uhm...

You can use the lazy segment tree + treap (or any other balanced tree) to solve it in $$$\mathcal O(\log^2 n)$$$ per query. In implementation, you can build a balanced tree for each node in segment tree, and it controls the whole subtree of that node (and as you know, a subtree in segment tree means a interval). Evidently, every node in segment tree will be in $$$\mathcal O(\log n)$$$ balanced trees, so it has a right complexity.

To make the change, you can do it like the simple lazy segment tree. So you can maintain a value $$$add$$$ in segment tree which means "how much this subtree of the node (a interval in fact) add/subtract". When you query, you also just do it like the simple lazy segment tree, but on each node, you should query the rank of $$$-add$$$, because now $$$-add$$$ is $$$0$$$ in fact.