The maximum amount of non-decreasing subsequence in an array using fenwick tree or BIT

The maximum amount can be found using a dynamic programming algorithm. Scan the array and for each element add its value to the largest sum of the subsequence that is valid (the subsequence ends with a value not greater than this element).

An effective implementation needs some way to quickly find the maximum value in a given subrange. To do this, you can use the extended binary search tree. The Fenwick tree is simply an efficient implementation of the extended binary search tree. The most common use of the Fenwick tree is to find the sum of the values ​​in a sub-range. The trivial modification allows you to use it to find the maximum of the subband (this works because in this particular case the values ​​in the Fenwick tree never decrease).

See this Python code for more details:

array = [1, 4, 4, 2, 2, 3, 3, 1]

numbers = sorted(set(array))
n = len(numbers)
indexes = {numbers[v]:v+1 for v in range(0, n)}
n += 1
bit = [0] * n
result = 0

for x in array:
    pos = indexes[x]
    i = pos
    maximum = 0
    while i != 0:
        maximum = max(maximum, bit[i])
        i = i & (i-1)
    x += maximum
    i = pos
    while i < n:
        bit[i] = max(bit[i], x)
        i += i & -i
    result = max(result, x)

print(result)

indexes . while . while Fenwick .

. , .

- O (N log N). - O (N).