How to quickly check if a bracket sequence is correct?

Question

Algorithms

Let's say there is some correct joint venture - S .
Then replace any one of its brackets with the opposite one ( "(" replace with ")" , and ")" with "(" ).
Now S is not a valid bracket sequence.
Next, we again invert some (already different) bracket.
Is it possible at this step to check the sequence for correctness in constant time (in the extreme case, for the logarithm-e)?
For example:
1. Beginning: S = (()())
2. First replacement - character inversion 3: S = (((())
3. The second replacement is the inversion of symbol 4: S = ((()))
At steps 1 and 3, the SP is correct, and at 2 it is incorrect.
Is it possible to check in non- linear time?
UPD:
The position of the inverted parenthesis is known

Answer 1

The only correctness condition is that the count of the number of closed brackets must not exceed the count of open ones. Store for each position the address of the nearest one to the right with a one ("+1") or zero ("0") bill amount. Since the open-to-close inversion decrements all counters to the right until the second inversion by "-2", you only need to check if the second inversion was a paired one, and if there was a one/zero count cell in between.
PS Paired inversion, in which the left replacement from closing to opening, as in your example, seems to me always valid.

Answer 2

The problem is that:
1. Suppose you already have a structure in memory that somehow allows you to determine the correctness in n * log (n).
2. You changed the parenthesis ( at the very beginning.
3. Now you already have a new sequence, you must change your structure so that it answers correctly about the new sequence.
4. But in order to change, you obviously have to forgive everyone else on the right parentheses, because the modified parenthesis changes the value of the parentheses on the right, but does not change anything on the left
5. You need O(n) time to go through
6. So there is no such structure :P
Nicely I proved it to you.

Answer 3

This is the criterion.
1. The balance ( and ) must be preserved.
2. a) Either the degenerate case (we change the parenthesis twice to the opposite one);
b) either ) → ( comes before ( → ) ;
c) or the nesting level of both brackets is at least 3, while they sit in common brackets of the 2nd level.
Because of 2v without preprocessing for O (n) it is impossible to check. But preprocessing is good if we solve a bunch of such requests, and this is a separate issue. In this case, it is probably better to use a slicing tree that processes each request in log n. So far, the algorithm is not completely clear to me; if you say that the task is really about a bunch of requests, I’ll think about it ..

Answer 4

1. If the sequence is initially correct - any inversion leads to its damage;
   If at least one of the above is not true, then the sequence is not correct, and their verification requires constant time.
   If everything is done, you need to use an additional structure and the following algorithm:
   Can't think of anything faster. The only subtle point is the check in the last paragraph, since in various cases it can take both constant time and O(k), where k is strictly less than n and is a logarithm in the average case.