Skip to content

Fenwick Tree

Table of Contents

307. Range Sum Query - Mutable

3072. Distribute Elements Into Two Arrays II

3187. Peaks in Array

1649. Create Sorted Array through Instructions

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, divide and conquer, binary indexed tree, segment tree, merge sort, ordered set

1626. Best Team With No Conflicts

1626. Best Team With No Conflicts - Python Solution
from typing import List


# DP - LIS
def bestTeamScore(scores: List[int], ages: List[int]) -> int:
    n = len(scores)
    pairs = sorted(zip(scores, ages))  # sort
    dp = [0 for _ in range(n)]

    # LIS
    for i in range(n):
        for j in range(i):
            if pairs[i][1] >= pairs[j][1]:
                dp[i] = max(dp[i], dp[j])
        dp[i] += pairs[i][0]

    return max(dp)


if __name__ == "__main__":
    assert bestTeamScore([1, 3, 5, 10, 15], [1, 2, 3, 4, 5]) == 34
    assert bestTeamScore([4, 5, 6, 5], [2, 1, 2, 1]) == 16

1409. Queries on a Permutation With Key

2250. Count Number of Rectangles Containing Each Point

2179. Count Good Triplets in an Array

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, divide and conquer, binary indexed tree, segment tree, merge sort, ordered set

1395. Count Number of Teams

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, dynamic programming, binary indexed tree, segment tree

2659. Make Array Empty

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, greedy, binary indexed tree, segment tree, sorting, ordered set

2653. Sliding Subarray Beauty

1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

2926. Maximum Balanced Subsequence Sum

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, dynamic programming, binary indexed tree, segment tree

2736. Maximum Sum Queries

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, stack, binary indexed tree, segment tree, sorting, monotonic stack

3382. Maximum Area Rectangle With Point Constraints II

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, math, binary indexed tree, segment tree, geometry, sorting

3245. Alternating Groups III

1756. Design Most Recently Used Queue

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, hash table, stack, design, binary indexed tree, ordered set

2519. Count the Number of K-Big Indices

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, binary search, divide and conquer, binary indexed tree, segment tree, merge sort, ordered set

2613. Beautiful Pairs

  • LeetCode | LeetCode CH (Hard)

  • Tags: array, math, divide and conquer, geometry, sorting, ordered set

2921. Maximum Profitable Triplets With Increasing Prices II

308. Range Sum Query 2D - Mutable

  • LeetCode | LeetCode CH (Medium)

  • Tags: array, design, binary indexed tree, segment tree, matrix

Comments